시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 43 17 6 23.077%

문제

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

예제 입력 1

3

예제 출력 1

14

예제 입력 2

71

예제 출력 2

563150