题目链接：HDOJ-3037

  这道题关键之处在于式子的推导，只要把式子推导出来了，就可以直接套用Lucas的模板，从而求出答案。那么，公式要怎么求呢？

  首先，问题要求的是从n棵树中收集不超过m个果实(原本以为是将不多于m个果实放到n棵树中......这题目表达有问题啊！)。也就是说，问题其实是求方程x1+x2+x3+···+xn=m的非负整数解的个数。那么我们要怎求呢？   首先，如果是求正整数解的个数，那我们可以直接用最简单的隔板法，即C(m-1,n-1);但这里求的是非负整数解，也就是说x1，x2，···,xn中的一个或多个可以为0。这种情况下，我们仍可以用隔板法来计算。方法是，将求非负整数解这一个问题转化为求正整数解，也就是将每一个x(x1,x2,···,xm)都加上1，构造一个新的方程y1+y2+···+yn=m(yi=xi+1)。显然，由于方程是线性的，故新方程的正整数解的个数等于原方程的非负整数解的个数。而新方程的解的个数为C((m+n)-1,n-1)=C((m+n)-1,m)。

  而我们要求的实际上是(∑(i=0,m)C(m+n-1,i))%p，根据公式C(n,k)=C(n-1,k-1)+C(n-1,k)(上取大，下加一),可得到(∑(i=0,m)C(m+n-1,i))%p=C(m+n,m)%p。又因为p为质数，故用Lucas即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;
ll powq(ll a,ll b,ll p)
{
    ll ans=1;a%=p;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}
ll inv(ll a,ll p)
{
    return powq(a,p-2,p);
}
ll comb(ll n,ll m,ll p)
{
    if(n<m)        return 0;
    ll up=1;
    ll down=1;
    for(int i=n-m+1;i<=n;i++)        up=(up*i)%p;
    for(int i=1;i<=m;i++)        down=(down*i)%p;
    return up*inv(down,p)%p;
}
ll lucas(ll n,ll m,ll p)
{
    return !n?1:lucas(n/p,m/p,p)*comb(n%p,m%p,p)%p;
}
int main()
{
    ll m,n,p;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %lld %lld",&n,&m,&p);     
        ll ans=lucas(n+m,n,p);
        printf("%lld\n",ans);
    }
    return 0;
}