給出組合數(shù) C(n,m) 表示從 n 個元素中選出 m 個元素的方案數(shù)。例如 C(5,2)=10,C(4,2)=6?？墒钱?n,m 比較大的時候，C(n,m) 很大。于是 xiaobo 希望你輸出 C(n,m)modp 的值。

輸入數(shù)據(jù)第一行是一個正整數(shù) T，表示數(shù)據(jù)組數(shù)；
接下來是 T 組數(shù)據(jù)，每組數(shù)據(jù)有 3 個正整數(shù) n,m,p。

對于每組數(shù)據(jù)，輸出一個正整數(shù)，表示 C(n,m) mod p 的結(jié)果。

2
5 2 3
5 2 61

1
10

數(shù)據(jù)范圍與提示：

對于所有數(shù)據(jù)，1≤m≤n≤10⁹，m≤10⁴，m<p<10⁹ ，p 是素數(shù)。