Congruence Equation

소수 p가 최대 10^15로 주어질 때 1 ≤ a, b ≤ p(p-1)이고 a^b ≡ b^a (mod p)인 순서쌍 (a,b)의 개수를 10^9+7로 나눈 나머지를 구한다.

어려움8정수론수학조합론구현아직 제출이 없습니다시간 제한1초메모리 제한256 MB

문제 설명

예제2

소수 $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$ 로 나눈 나머지를 출력한다.