합동방정식

시간 제한1초메모리 제한256 MB

요약

1 이상 p(p-1) 이하의 순서쌍 (a, b) 중에서 a^b ≡ b^a (mod p)인 개수를 세어 10^9+7로 나눈 나머지를 구합니다.

문제

소수 $p$ 에 대하여 합동방정식 $a^b \equiv b^a \pmod{p}$ 와 부등식 $1 \le a, b \le p(p-1)$ 을 만족하는 자연수 순서쌍 $(a,b)$ 의 개수를 구해보자.

값이 커질 수 있으니 $10^9+7$ 로 나눈 나머지를 출력한다.

소수 $p$ 가 첫 줄에 입력된다. ( $2 \le p \le 10^{15}$ )

조건을 만족하는 순서쌍의 개수를 $10^9+7$ 로 나눈 나머지를 출력한다.