方程

【题目描述】

hyc 碰到了一个难题，请你来帮忙解决。

对于不定方程a1+a2+a3+……+ak=g(x) ，其中K.>=2,k是正整数 , x 是正整数 ,

g(x)=x^x mod 1000 , x,k 是给定的数 . 我们要求的是这个不定方程的正整数解组数 .

举例来说 , 当 k=3,x=2 时 ,g(x)=4, 原方程即 A1+A2+A3=4 .

这个方程的正整数解有 3 组 . 分别为 (A1,A2,A3) = （2，1，1），（1，2，1），（1，1，2）.

【输入文件】

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

【输出文件】

有且只有一行 , 为方程的正整数解组数 .

【样例输入】

3 2

【样例输出】

3

【数据范围】

对于 40% 的数据 , ans<= 10^16 ;

对于 100% 的数据 , k<=100 , x<= 2^31-1 ,k<=g(x)。