No testdata at current.

时间限制： 3.0 秒

空间限制： 512 MB

题目描述

首先这道题目不是小葱出的。

C 先生现在有 $N$ 个互不相同的苹果十号。

C 先生想选出其中的 $M$ 个，送给他的女朋友 S 小姐。

C 先生想知道有多少种不同的送礼物方案，这里认为两种方案不同，当且仅当存在一个苹果十号只在其中一个方案里被送出去。

C 先生知道 S 小姐的幸运数字是 $P$，所以他只想知道方案数对 $P$ 的余数。

输入格式

从标准输入读入数据。

输入第一行包含一个整数 $T~(1 \le T \le 15)$，表示数据组数。

接下来 $T$ 行，每行三个整数 $N, M, P$，描述一组数据。

输出格式

输出到标准输出。

对每组数据，输出一行一个整数，表示答案。

1
10 9 9

1

样例 1 解释

$C(10, 9) = 10 \equiv 1 \pmod 9$。

子任务

对所有数据，保证 $1 \le T \le 15,~0 \le N, M \le 10^9 + 7,~1\le P\le 10^9+7,~M \le N$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 子任务 1（15 分）：保证 $N, M \le 2000$，取模前的答案不超过 $10^7$。
• 子任务 2（10 分）：保证 $N, M \le 2000$，取模前的答案不超过 $2 \times 10^{18}$。
• 子任务 3（15 分）：保证 $N, M \le 2000$。
• 子任务 4（10 分）：$N, M \le P \le 3 \times 10^7$，且 $P$ 为质数。
• 子任务 5（10 分）：$P \le 10^7$，且 $P$ 是一个质数。
• 子任务 6（10 分）：$P$ 只含有一种质因子，且 $P \le 10^7$。
• 子任务 7（15 分）：$P$ 不含有平方因子，且 $P$ 的每个质因子不超过 $10^7$。
• 子任务 8（15 分）：$P$ 只含有一种质因子，且 $P$ 不为质数。

提示

这里的 C 先生和 S 小姐指的当然是 Computer Science 啦！