J21 例题-2 方程的解

题目描述

佳佳碰到了一个难题，请你来帮忙解决。对于不定方程 $a_1+a_2+\ldots+a_{k-1}+a_k=g(x)$，其中 $k \ge 2$且 $k \in N^*$， $x$ 是正整数，$g(x)=x^x \bmod 1000$（即 $x^x$ 除以 $1000$ 的余数）， $x,k$ 是给定的数。我们要求的是这个不定方程的正整数解组数。

举例来说，当 $k=3,x=2$ 时，方程的解分别为：

$\left\{\begin{array}{c}a_1 = 1\\a_2 = 1 \\a_3 = 2\end{array}\right.$$\left\{\begin{array}{c}a_1 = 1\\a_2 = 2 \\a_3 = 1\end{array}\right.$ $\left\{\begin{array}{c}a_1 = 2\\a_2 = 1 \\a_3 = 1\end{array}\right.$

输入格式

有且只有一行，为用空格隔开的两个正整数，依次为 $k,x$ 。

输出格式

有且只有一行，为方程的正整数解组数。

样例输入

3 2

样例输出

3

样例分析

如上所述。

数据范围

对于 $40\%$ 的数据：答案不超过 $10^{16}$。

对于 $100\%$ 的数据，$1 \leq k \leq 100,1 \leq x < 2^{31},k \leq g(x)$。