SOLVE

LATER

Modulo Fermat's Theorem

/

It is well-known that the equation: \(x^k + y^k = z^k\) has no positive solution for \(k \ge 3\). But what if we consider solution over a finite field. Now, the task you are given is related to that:

Given a prime \(P\), you are asked to count the number of positive integers \(k\) doesn't exceed \(L\) s.t. modulo equation \(x^k + y^k = z^k\ (modulo\ P)\) has solution \(0 < x, y, z < P\).

**Input Format**

A line contains two space-separated integers \(P, L\) as described above.

**Output Format**

Output answer in a single line.

**Constraints**

- \(1 \le P \le 10^6\)
- \(1 \le L \le 10^{18}\)

Explanation

Let's enumerate all possible values of \(k\):

- \(k = 1:\) there is a solution \((x, y, z) = (1, 1, 2)\).
- \(k = 2:\) there is no solution.
- \(k = 3:\) this is a solution \((x, y, z) = (1, 3, 2)\).
- \(k = 4:\) there is no solution.

So, answer is \(2\).

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...