【问题描述】

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

对于不定方程a1+a2+…+a(k-1)+ak=g(x)，其中k>=2且k属于N*, 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).

【输入文件】

输入文件equation.in有且只有一行.为用空格隔开的两个正整数,依次为k,x.

【输出文件】

输入文件equation.out有且只有一行,为方程的正整数解组数.

【样例输入】

3 2

【样例输出】

3

【数据范围】

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

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