Lucas' theorem
In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient
by a prime number p in terms of the base p expansions of the integers m and n. ----wiki
##表达式
对于非负整数m、n和素数p，如果有：
则有下式成立：
##牛刀小试
题目链接：[hdu-3037](http://acm.hdu.edu.cn/showproblem.php?pid=3037)
题目大意：求在n棵树上摘不超过m颗豆子的方案，结果对p取模。
解题思路：
首先，n棵树上摘m课豆子的方案数相当于从n个数中可重复的选m个数的组合数，为。那么现在就是求
代码：
```c++
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 100001;
LL mod;
LL jc[N];
LL quick(LL a, LL b)
{
LL c = 1;
while(b)
{
if(b&1) c = c * a % mod;
b >>= 1;
a = a * a % mod;
}
return c;
}
LL NY(LL a)
{
return quick(a, mod-2);
}
void init()
{
jc[0] = 1;
for(LL i=1; i<mod; i++)
{
jc[i] = i * jc[i-1] % mod;
}
}
LL C(LL n, LL m)
{
if(n < m) return 0;
return jc[n] % mod * NY(jc[m]) % mod * NY(jc[n-m]) % mod;
}
LL Lucas(LL n, LL m)
{
if(!m) return 1;
return Lucas(n/mod, m/mod) * C(n%mod, m%mod) % mod;
}
int main()
{
LL n, m;
int t;
scanf("%d", &t);
while(t--)
{
scanf("%I64d %I64d %I64d", &n, &m, &mod);
init();
printf("%I64d\n", Lucas(n+m, m));
}
return 0;
}