对于每组数据输出一个正整数，表示C(n,m) mod p的结果

分析：设那么上述方程解的个數就与同余方程组：的解等价。

设同于方程的解分别是：那么原方程的解的个数就是

所以现在的关键问题是求方程：的解个数。

这个方程我们需要分3类讨论：

对于这种情况如果方程的某个解设为，那么一定有可以得到，即

所以方程的解个数就是：也就是

这样也就是說p|B，设，本方程有解的充要条件是A|t

所以进一步有：，因为这样又转化为第三种情况了。

那么我们要求指标；求指标的话又要求原根并且奇素数p的原根也是p^a的原根，所以说求个p的原根就好了

且如果有解，则解的个数为(A,φ(p^a))

如果不知道原根与指标的现在就补一下吧：

萣义一：设m>1,(a,m)=1,则使得成立的最小正整数r，称为a对模m的指数或者a对模m的阶，记为

定义二：若则a是模m的原根。

定理二：如果大于1的正整数m有原根那么它一共有个不同的原根。

定理三：模m有原根的必要条件是m=24，p^a或者2p^a其中p是奇素数。

定理四：设m>1,所有不同的奇因数是(g,m)=1，则g是模m的原根的充要条件是：

现在我们来研究同余式  (a,m)=1有解的条件以及解数，注意现在的m=p^a或者2p^a，g是模m的一个原根

若(n,c)=d ,(a,m)=1，则上述同余式有解的充要条件是d|inda并且在有解的条件下，解数为d

在模m的一个简化剩余系中，n次剩余的个数是

定理一：若r通过模c的最小非负完全剩余系则g^r通過模m的一个简化剩余系。

证明：g是模m的一个原根则对模m两两不同余，又因为(g,m)=1所以(g^r,m)=1

因此是模m的一个简化剩余系。

定理一：设a是一整数(a,m)=1，若对模m的一个原根g有一整数r存在使得下式

成立，则r就叫做以g为底的a对模m的一个指标,记为r=inda