题目描述
佳佳碰到了一个难题，请你来帮忙解决。对于不定方程
a_1+a_2+\cdots +a_{k-1}+a_k=g(x)
a1
+a2
+⋯+ak−1
+ak
=g(x)，其中
k\ge 2
k≥2 且
k\in \mathbb{N}^*
k∈N∗，
x
x 是正整数，
g(x)=x^x \bmod 1000
g(x)=xxmod1000（即
x^x
xx 除以
1000
1000 的余数），
x,k
x,k 是给定的数。我们要求的是这个不定方程的正整数解组数。
举例来说，当
k=3,x=2
k=3,x=2 时，方程的解分别为：
a1=1 a2=1 a3=2
a1=1 a2=2 a3=1
a1=2 a2=1 a3=1
输入
有且只有一行，为用空格隔开的两个正整数，依次为
k,x
k,x。
输出
有且只有一行，为方程的正整数解组数。
样例输入
3 2
样例输出
3
提示
数据范围与提示
对于
40\%
40% 数据，答案不超过
10^{16}
1016；
对于全部数据，
1\le k\le 100,1\le x\lt 2^{31},k\le g(x)
1≤k≤100,1≤x<231,k≤g(x)。
来源/分类
ybttg 组合计数