Fermat Equation (Fermat)

Time limit0.5sMemory limit1024 MB

Summary

Given a prime p and exponent n, count triples (x,y,z) with entries in 0..p-1 such that x^n + y^n = z^n mod p.

Level: Medium7 of 10
Topics: Number theory, Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

Given a prime $p$ and a natural number $n \ge 1$ , write a program that finds the number $m$ of triples $(x, y, z)$ of integers $x, y, z$ ( $0 \le x, y, z \le p-1$ ) satisfying

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

Here $a \equiv b \pmod p$ means that $a - b$ is divisible by $p$ .

Input

The first line of the input contains a prime $p$ ( $p < 10000$ ). The second line contains a natural number $n$ ( $1 \le n \le 10000$ ).

Output

Print one line to standard output consisting of the single integer $m$ .

Hint

Note For the input data used in grading, the value of $m$ is less than $2^{31}$ .

Examples2

Example 1
Input
```
3
5
```
Expected output
```
9
```
Example 2
Input
```
19
21
```
Expected output
```
487
```