Description

Jiajia ran into a tough problem and asks you to help solve it. Consider the Diophantine 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, and $g(x) = x^x \bmod 1000$ (that is, the remainder of $x^x$ modulo $1000$). The numbers $x$ and $k$ are given. Your task is to find the number of solution tuples in positive integers to this equation.

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

Input Format

The input contains exactly one line with two positive integers separated by a space, namely $k, x$.

Output Format

Output exactly one line with the number of solution tuples in positive integers.

3 2

3

Hint

• For 40% of the testdata, $\mathit{ans} \le 10^{16}$.
• For 100% of the testdata, $k \le 100$, $x \le 2^{31}-1$, $k \le g(x)$.

NOI Journal 2010 Senior (01)

Translated by ChatGPT 5