方程的解

方程的解

Description

佳佳碰到了一个难题,请你来帮忙解决。对于不定方程 a1+a2+...+ak-1+ak=g(x),中k≥2且k∈N,x是正整数,g(x)=x^x mod 1000(即x^x除以1000的余数),x,k是给定的数。我们要求的是这个不定方程的正整数解组数。
举例来说,当k=3,x=2时,分别为(a1,a2,a3)=(2,1,1)’(1,2,1),(1,1,2)。 输入输出格式 输入格式:

Format

Input

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

Output

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

Sample 1

Input

3 2

Output

3

Limitation

1s, 64MiB for each test case.
对于40%的数据,ans<=10^16;
对于100%的数据,k<=100,x<=2^31-1,k<=g(x);

Source