페르마 방정식 (Fermat)

시간 제한0.5초메모리 제한1024 MB

요약

소수 p와 지수 n이 주어질 때 0 이상 p-1 이하의 정수 x, y, z에 대해 x^n + y^n ≡ z^n (mod p)를 만족하는 순서쌍의 개수를 구한다.

문제

소수 $p$ 와 자연수 $n \ge 1$ 이 주어졌을 때,

$x^n + y^n \equiv z^n \pmod p$

를 만족하는 정수 $x, y, z$ ( $0 \le x, y, z \le p-1$ )의 순서쌍 $(x, y, z)$ 의 개수 $m$ 을 구하는 프로그램을 작성하라. 여기서 $a \equiv b \pmod p$ 는 $a - b$ 가 $p$ 로 나누어떨어진다는 뜻이다.

입력의 첫째 줄에는 소수 $p$ ( $p < 10000$ )가 주어진다. 둘째 줄에는 자연수 $n$ ( $1 \le n \le 10000$ )이 주어진다.

표준 출력에 정수 $m$ 하나만으로 이루어진 한 줄을 출력하라.

주의 채점에 사용하는 입력 데이터에서 $m$ 의 값은 $2^{31}$ 보다 작다.