mod = 10**9+7 class NumberOfCases: def __init__(self, N, mod): self.mod = mod self.fact = [0] * (N+1) self.factinv = [0] * (N+1) self.fact[0] = 1 self.factinv[0] = 1 for i in range(1,N+1): self.fact[i] = (i * self.fact[i-1]) % self.mod self.factinv[i] = self.bin_power(self.fact[i], self.mod - 2) def bin_power(self, x, k): ret = 1 while k > 0: if k & 1: ret = ret * x % self.mod x = x * x % self.mod k >>= 1 return ret def comb(self, n, r): if n < r or r < 0: return 0 return self.fact[n] * self.factinv[r] % self.mod * self.factinv[n-r] % self.mod def perm(self, n, r): if n < r or r < 0: return 0 return self.fact[n] * self.factinv[n-r] % self.mod def comb_h(self, n, r): return self.comb(n+r-1, r) def solve(): S = input() x = eval(S[1:]) if S[0] == 'C': print(C.comb(x[0], x[1])) if S[0] == 'P': print(C.perm(x[0], x[1])) if S[0] == 'H': print(C.comb_h(x[0], x[1])) M = 10**6 C = NumberOfCases(M*2, mod) T = int(input()) for _ in range(T): solve()