3. Modular Arithmetic
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Vasya is studying modular arithmetic. To practice, he calculated the sum $$$1^1 + 2^2 + \dots + n^n$$$ modulo $$$m$$$. In other words, he found the remainder when this sum is divided by $$$m$$$.

Vasya obtained the result $$$r$$$. However, he made a mistake during his calculation — he omitted one of the terms. Determine the index of the term that he left out.

Input

Three integers $$$n$$$, $$$m$$$, and $$$r$$$ are provided, each on a separate line ($$$2 \le n \le 10^5$$$, $$$1 \le m \le 10^9$$$, $$$0 \le r \lt m$$$).

Output

Output an integer from $$$1$$$ to $$$n$$$ representing the index of the missing term. If there are multiple valid answers, output the smallest one. If no solution exists, output $$$0$$$.

Scoring

Subtask 1 (up to 30 points): $$$n \le 5$$$

Subtask 2 (up to 30 points): $$$n \le 100$$$

Subtask 3 (up to 40 points): $$$n \le 10^5$$$

Examples
Input
3
10
8
Output
2
Input
3
10
2
Output
0