#include #include #include #include using namespace std; #define REP(i,s,e) for (i = s; i <= e; i++) #define rep(i,n) REP (i,0,(int)(n)-1) #define RREP(i,s,e) for (i = s; i >= e; i--) #define rrep(i,n) RREP (i,(int)(n)-1,0) #define INF (int)1e8 #define MOD (int)(1e9+7) typedef long long ll; int frac[1000100]; int inv(ll x) { int n = MOD-2; ll ret = 1; while (n > 0) { if (n % 2) ret *= x, ret %= MOD; x *= x; x %= MOD; n /= 2; } return ret; } int C(int n, int k) { if (n < k) return 0; else return 1LL * frac[n] * inv(frac[k]) % MOD * inv(frac[n-k]) % MOD; } int P(int n, int k) { if (n < k) return 0; else return 1LL * frac[n] * inv(frac[n-k]) % MOD; } int H(int n, int k) { return C(n+k-1,k); } int main(void) { int t; ll i; frac[0] = 1; REP (i,1,1000000) frac[i] = (frac[i-1] * i) % MOD; cin >> t; while (t--) { string s; int n, k; size_t pos; cin >> s; n = stoi(s.substr(2),&pos); k = stoi(s.substr(3+pos)); if (s[0] == 'C') cout << C(n,k) << endl; else if (s[0] == 'P') cout << P(n,k) << endl; else if (s[0] == 'H') cout << H(n,k) << endl; } return 0; }