虽然冬天很远，松鼠不得不日夜工作以节省豆类。 他们需要大量的食物来度过这漫长的寒冷日子。 一段时间后，松鼠家庭认为他们必须解决问题。 他们认为他们会在不同的树木中储存豆子。 然而，由于现在的食物不足，他们只能吃到豆子。 他们想知道有多少种方法可以在n树中保存不超过m个bean（它们是相同的）。

现在他们求助于你，你应该给他们答案。 结果可能非常巨大; 你应该输出模p的结果，因为松鼠无法识别大数。

Input

第一行包含一个整数T，表示案例数。

然后是T行，每行包含三个整数n，m，p，意味着松鼠将在n个不同的树中保存不超过m个相同的bean，1 <= n，m <= 1000000000,1

 

Output

你应该输出模p的答案。

Sample Input

2
1 2 5
2 1 5

Sample Output

3
3

Hint

提示：

对于样本1，松鼠将在一棵树中放置不超过2个豆。 由于树木不同，我们可以将它们标记为1,2 ......等等。

3种方法是：不放豆，将1个豆放在树1中，将2个豆放在树1中。对于样品2，3种方法是：   没有豆，把1豆放在树1中，把1豆放在树2中。

题解：题目是让求C（n+m,n），直接作为模板使用就可以了

#include <bits/stdc++.h>
using namespace std;
long long p,m1,n1;
long long Pow(long long a,long long b)
{
    long long ans=1;
    while(b)
    {
        if(b&1)
        {
            b--;
            ans=(ans*a)%p;
        }
        b>>=1;
        a=(a*a)%p;
    }
    return ans;
}
long long C(long long n,long long m)
{
    if(n<m)
        return 0;
    long long a=1,b=1;
    while(m)
    {
        a=(a*n)%p;
        b=(b*m)%p;
        m--;
        n--;
    }
    return (a*Pow(b,p-2))%p;
}
long long Lucas(long long n,long long m)
{
    if(m==0)
        return 1;
    return Lucas(n/p,m/p)*C(n%p,m%p)%p;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld%lld",&n1,&m1,&p);
        printf("%lld\n",Lucas(n1+m1,n1));  
    }
    return 0;
}