#include #include #include #include #include #include #include #include #include #define repd(i,a,b) for (int i=(a);i<(b);i++) #define rep(i,n) repd(i,0,n) #define PRIME 1000000007 #define SIZE 2000000 typedef long long ll; using namespace std; ll f[SIZE] = {0}; int inputValue(){ int a; cin >> a; return a; }; void inputArray(int * p, int a){ rep(i, a){ cin >> p[i]; } }; void inputVector(vector * p, int a){ rep(i, a){ int input; cin >> input; p -> push_back(input); } } template void output(T a, int precision) { if(precision > 0){ cout << setprecision(precision) << a << "\n"; } else{ cout << a << "\n"; } } ll power(ll a, int p, int mod){ if (p == 0) return 1; if (p % 2 == 1){ return a * power(a, p - 1, mod) % mod; } long long c = power(a, p / 2, mod); return c * c % mod; } ll inverse(ll a, int mod){ return power(a, mod - 2, mod); } ll combination(int n, int k, int mod){ if (n < k) return 0; ll temp = f[n] * inverse(f[k], mod) % mod; return temp * inverse(f[n - k], mod) % mod; } ll permutation(int n, int k, int mod){ if (n < k) return 0; return f[n] * inverse(f[n - k], mod) % mod; } ll homogeneous(int n, int k, int mod){ return combination(n + k - 1, k, mod); } int main(int argc, const char * argv[]) { f[0] = 1; repd(i, 1, SIZE){ f[i] = f[i - 1] * i % PRIME; } int T = inputValue(); rep(i, T){ char c; cin >> c; cin.ignore(); int N = inputValue(); cin.ignore(); int K = inputValue(); cin.ignore(); if(c == 'C') output(combination(N, K, PRIME), 0); if(c == 'P') output(permutation(N, K, PRIME), 0); if(c == 'H') output(homogeneous(N, K, PRIME), 0); } return 0; }