Description

Jiajia encountered a challenging problem and needs your help to solve it. Consider the indeterminate equation $a_1 + a_2 + \cdots + a_{k-1} + a_k = g(x)$, where $k \ge 2$ and $k \in \mathbb{N}^*$, $x$ is a positive integer, $g(x) = x^x \bmod 1000$ (i.e., the remainder when $x^x$ is divided by 1000), and $x, k$ are given. We are to determine the number of positive integer solutions to this equation.

For example, when $k=3, x=2$, the solutions to the equation are:

$$\begin{cases} a_1=1\\ a_2=1\\ a_3=2 \end{cases} \ \ \ \ \begin{cases} a_1=1\\ a_2=2\\ a_3=1 \end{cases} \ \ \ \ \begin{cases} a_1=2\\ a_2=1\\ a_3=1 \end{cases} $$

Input Format

There is one and only one line containing two positive integers separated by a space, representing $k$ and $x$ respectively.

Output Format

Output one and only one line, the number of positive integer solutions to the equation.

Sample 1

3 2

3

Data Range and Hint

For $40\%$ of the data, the answer does not exceed $10^{16}$;
For all data, $1 \le k \le 100, 1 \le x \lt 2^{31}, k \le g(x)$.