#include #include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) const int MOD = 1000000007; // 998244353; /*-------------------------------------------------*/ struct Combinatorics { Combinatorics(int MAX = 5000000, long long mod_ = MOD) : mod(mod_) { MAX <<= 1; fact.resize(MAX + 1); fact_inv.resize(MAX + 1); fact[0] = 1; FOR(i, 1, MAX + 1) fact[i] = fact[i - 1] * i % mod; fact_inv[MAX] = mod_inv(fact[MAX]); for (int i = MAX; i > 0; --i) fact_inv[i - 1] = fact_inv[i] * i % mod; } inline long long nCk(int n, int k) { if (n < 0 || n < k || k < 0) return 0; return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod; } inline long long nPk(int n, int k) { if (n < 0 || n < k || k < 0) return 0; return fact[n] * fact_inv[n - k] % mod; } inline long long nHk(int n, int k) { if (n < 0 || k < 0) return 0; return (k == 0 ? 1 % mod : nCk(n + k - 1, k)); } private: long long mod; vector fact, fact_inv; long long mod_pow(long long base, long long exponent, long long mod = MOD) { base %= mod; long long res = 1; while (exponent > 0) { if (exponent & 1) (res *= base) %= mod; (base *= base) %= mod; exponent >>= 1; } return res; } long long mod_inv(long long a, long long mod = MOD) { return mod_pow(a % mod, mod - 2, mod); } }; int main() { cin.tie(0); ios::sync_with_stdio(false); // freopen("input.txt", "r", stdin); Combinatorics com(1000000); int t; cin >> t; while (t--) { string s; cin >> s; string n = ""; int idx = 2; for (; ; ++idx) { char c = s[idx]; if (c == ',') break; n += c; } string k = s.substr(idx + 1); if (s[0] == 'C') cout << com.nCk(stoi(n), stoi(k)); else if (s[0] == 'P') cout << com.nPk(stoi(n), stoi(k)); else cout << com.nHk(stoi(n), stoi(k)); cout << '\n'; } return 0; }