505010 - 卢卡斯定理

【题目描述】卢卡斯定理(lucas)

给定整数n,m,p的值,求出C_(n+m)^n mod p的值,保证p为质数。

输入

第一行一个整数T(1≤T≤10),表示数据组数。 每组数据为一行三个整数n,m,p(1≤n,m,p≤10^5)。

输出

对于每组数据,输出一行一个整数,表示所求的值。

样例

输入

    2
1 2 5
2 1 5

输出

3
3
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题