def init_factorials(N, mod): '''[n! % mod for n in range(N)] を返す。 ''' f = 1 fac = [1] * N for i in range(1, N): f *= i f %= mod fac[i] = f return fac def inv(a, m): ''' a * b = 1 (mod m) となる b を返す。 m は素数とする。 b = a**(m-2) (mod m) となることが知られており、これを使って計算している。 ''' n = m - 2 b = bin(n)[2:][-1::-1] ret = 1 tmp = a if b[0] == '1': ret = a for bi in b[1:]: tmp *= tmp tmp %= m if bi == '1': ret *= tmp ret %= m return ret def nCb(n, b, mod, fac): ''' nCb % mod を返す。 mod が素数で、mod > n のときのみ有効。 ''' if b > n: return 0 num = fac[n] r1 = inv(fac[b], mod) r2 = inv(fac[n-b], mod) return (num * r1 * r2) % mod def nPb(n, b, mod, fac): if b > n: return 0 num = fac[n] r = inv(fac[n-b], mod) return (num * r) % mod def nHb(n, b, mod, fac): return nCb(b+n-1, b, mod, fac) mod = 10**9 + 7 fac = init_factorials(2 * 10**6+5, mod) T = int(input()) for t in range(T): S = input() N, K = map(int, S[2:-1].split(',')) op = S[0] if op == 'C': print(nCb(N, K, mod, fac)) elif op == 'P': print(nPb(N, K, mod, fac)) else: print(nHb(N, K, mod, fac))