D. G27*【组合数：lucas定理】$C_n ^m \bmod p$（p是素数，p不变）

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

给定整数 $n, m$ 的值，求出 $C_n ^m \bmod 10007$ 的值。

注: $C$ 表示组合数。

第一行一个整数 $T$ ，表示数据组数。

对于每组数据：一行，三个整数 $n,m$ 。

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

对于 $100\%$ 的数据， $1 \leq n,m,p \leq 10^5$ ， $1 \leq T \leq 10$ 。