Problem Statement

Let $C(N,K)$ denote the number of ways to choose $K$ distinct integers from the $N$ integers between $1$ and $N$, inclusive.
Let $P(N,K)$ denote the number of ways to choose $K$ distinct integers from the $N$ integers between $1$ and $N$, inclusive, and arrange them in order.
Let $H(N,K)$ denote the number of ways to choose $K$ integers, with repetition allowed, from the $N$ integers between $1$ and $N$, inclusive.
(Concrete examples are given in the explanation of Sample 1; refer to it if necessary.)
You are given $T$ queries. Each query gives one of $C(N,K), P(N,K), H(N,K)$. Write a program that computes its value ${\rm mod}\ 10^9+7$.

Input

$T$
$S_1$
$S_2$
$\vdots$
$S_T$

$1 \leq T \leq 10^5$
$S_k$ has one of the forms $C(N,K), P(N,K), H(N,K)$, where $N,K$ satisfy $0 \leq N,K \leq 10^6$
The input does not contain any extra spaces or the like. See the samples for the detailed input format

Output

For each query, output its value ${\rm mod}\ 10^9+7$ on $1$ line.

Sample

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

6
5
6
3628800
6

5
C(1,1000000)
C(0,0)
P(1000000,1000000)
P(1,10)
H(1,1000)

0
1
641102369
0
1