佳佳碰到了一个难题，请你来帮忙解决。对于不定方程 a_1+a_2+\cdots +a_{k-1}+a_k=g(x) ，其中 k\ge 2 且 k\in \mathbb{N}^* ， x 是正整数， g(x)=x^x \bmod 1000 （即 x^x 除以 1000 的余数）， x,k 是给定的数。我们要求的是这个不定方程的正整数解组数。
举例来说，当 k=3,x=2 时，方程的解分别为：
\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}
有且只有一行，为用空格隔开的两个正整数，依次为 k,x 。
有且只有一行，为方程的正整数解组数。
3 2
3
对于 40\% 数据，答案不超过 10^{16} ； 对于全部数据， 1\le k\le 100,1\le x\lt 2^{31},k\le g(x) 。