2933: 「一本通 6.6 练习 2」方程的解

Memory Limit：512 MB Time Limit：1 S
Judge Style：Text Compare Creator：
Submit：42 Solved：17

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)。


Input

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

Output

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

Sample Input Copy 

3 2

Sample Output Copy 

3

HINT


对于40%的数据，ans≤10^16；
对于100%的数据，k≤100，x≤2^31-1，k≤g(x)。
NOI导刊2010提高


Source/Category

加入题单

算法标签：