佳佳碰到了一个难题,请你来帮忙解决。对于不定方程 a_1+a_2+⋯+a_{k−1}+ak=g(x) ,其中 k≥2 且 k∈N^∗ , x 是正整数, g(x)=x^xmod1000 (即 x^x 除以 1000 的余数), x,k 是给定的数。我们要求的是这个不定方程的正整数解组数。
举例来说,当 k=3,x=2 时,方程的解分别为:
有且只有一行,为用空格隔开的两个正整数,依次为 k,x。
k,x
有且只有一行,为方程的正整数解组数。
3 2
3
数据范围与提示:
对于 40% 数据,答案不超过 10^{16} ;
对于全部数据, 1≤k≤100,1≤x<2^{31},k≤g(x) 。