#include "bits/stdc++.h" using namespace std; #ifdef _DEBUG #include "dump.hpp" #else #define dump(...) #endif //#define int long long #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(c) begin(c),end(c) const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f; const int MOD = 1'000'000'007; template bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; } template struct ModInt { static const int kMod = MOD; unsigned x; ModInt() :x(0) {} ModInt(signed x_) { x_ %= MOD; if (x_ < 0)x_ += MOD; x = x_; } ModInt(signed long long x_) { x_ %= MOD; if (x_ < 0)x_ += MOD; x = x_; } int get()const { return (int)x; } ModInt &operator+=(ModInt m) { if ((x += m.x) >= MOD)x -= MOD; return *this; } ModInt &operator-=(ModInt m) { if ((x += MOD - m.x) >= MOD)x -= MOD; return *this; } ModInt &operator*=(ModInt m) { x = (unsigned long long)x*m.x%MOD; return *this; } ModInt &operator/=(ModInt m) { return *this *= m.inverse(); } ModInt operator+(ModInt m)const { return ModInt(*this) += m; } ModInt operator-(ModInt m)const { return ModInt(*this) -= m; } ModInt operator*(ModInt m)const { return ModInt(*this) *= m; } ModInt operator/(ModInt m)const { return ModInt(*this) /= m; } ModInt operator-()const { return ModInt(kMod - x); } bool operator==(ModInt m)const { return x == m.x; } bool operator!=(ModInt m)const { return x != m.x; } ModInt inverse()const { signed a = x, b = MOD, u = 1, v = 0; while (b) { signed t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } if (u < 0)u += MOD; return ModInt(u); } }; template ostream &operator<<(ostream &os, const ModInt &m) { return os << m.x; } template istream &operator>>(istream &is, ModInt &m) { signed long long s; is >> s; m = ModInt(s); return is; }; using mint = ModInt; template ModInt pow(ModInt a, unsigned long long k) { ModInt r = 1; while (k) { if (k & 1)r *= a; a *= a; k >>= 1; } return r; } // n < 10^7 // 前計算 O(n) // 計算 O(1) vector fact, factinv; void precomputeFact(int n) { n = min(n, mint::kMod - 1); // N >= kMod => N! = 0 (mod kMod) fact.resize(n + 1); factinv.resize(n + 1); fact[0] = 1; for (int i = 1; i < n + 1; i++) fact[i] = fact[i - 1] * i; factinv[n] = fact[n].inverse(); for (int i = n; i >= 1; i--) factinv[i - 1] = factinv[i] * i; // ((i-1)!)^(-1) = (i!)^(-1) * i } mint binom(int n, int r) { if (n >= mint::kMod) return binom(n % mint::kMod, r % mint::kMod) * binom(n / mint::kMod, r / mint::kMod); return r > n ? 0 : fact[n] * factinv[n - r] * factinv[r]; } // O(r) mint binom_r(int n, int r) { mint ret = 1; for (int i = 0; i < r; i++) { ret *= n - i; ret /= i + 1; } return ret; } signed main() { cin.tie(0); ios::sync_with_stdio(false); int T; cin >> T; cin.ignore(); precomputeFact(2000000); rep(i, 0, T) { string s; cin >> s; dump(s); char a; int x, y; sscanf(s.c_str(), "%c(%d,%d)\n", &a, &x, &y); if (a == 'C') { cout << binom(x, y) << endl; } else if (a == 'P') { cout << binom(x, y)*fact[y] << endl; } else { cout << binom(x + y - 1, y) << endl; } } return 0; }