题目描述

你需要计算三种排列组合相关的数：

$C(N,K)$：从 $1 \sim N$ 中选择 $K$ 个不同的数，顺序无关，有多少种方法；

$P(N,K)$：从 $1 \sim N$ 中选择 $K$ 个不同的数，顺序有关，有多少种方法；

$H(N,K)$：从 $1 \sim N$ 中选择 $K$ 个数，可以相同，顺序无关，有多少种方法；

由于答案都看可能很大，只需要计算 $\bmod 10^9+7$ 的结果。

输入格式

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

后续 $T$ 行，每行一个字符串，如题面描述。具体可参考样例。

输出格式

输出 $T$ 行，每行一个要求的排列组合数 $\bmod 10^9+7$ 的结果。

样例输入输出

样例输入1

5
C(4,2)
C(5,1)
P(3,2)
P(10,10)
H(3,2)

样例输出1

6
5
6
3628800
6

样例说明 #1

$C(4,2)=6$，分别是 $\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}$。

$C(5,1)=5$，分别是 $\{1\},\{2\},\{3\},\{4\},\{5\}$。

$P(3,2)=6$，分别是 $\{1,2\},\{2,1\},\{1,3\},\{3,1\},\{2,3\},\{3,2\}$。

$P(10,10)=10!=3628800$。

$H(3,2)=6$，分别是 $\{1,1\},\{1,2\},\{1,3\},\{2,2\},\{2,3\},\{3,3\}$。

数据范围

10% 的数据，$T \le 10$，只有 $C(N,K)$。

另有 10% 的数据，$T \le 10$，只有 $P(N,K)$。

另有 10% 的数据，$T \le 10$，只有 $H(N,K)$。

另有 10% 的数据，$T \le 10$。

100% 的数据，$T \le 30000$，$0 \le N,K \le 10^6$。