P2187 [第六章例题6.3]组合
描述
给出组合数C(n,m),表示从n个元素中选出m个元素的方案。例如C(5,2)=10,C(4,2)=6。可是当n,m比较大的时候,C(n,m)很大!于是小波希望你输出C(n,m)mod p的值。
输入
输入数据的第一行是一个正整数T,表示数据数组(T≤100)。
接下来是T组数据,每组数据有3个正整数n,m,p(1≤m≤n≤109,m≤104,m<p<109,p是质素)。
接下来是T组数据,每组数据有3个正整数n,m,p(1≤m≤n≤109,m≤104,m<p<109,p是质素)。
输出
对于每组数据,输出一个正整数,表示C(n,m) mod p 的结果。
样例输入
2
5 2 3
5 2 61
样例输出
1 10