#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define MOD 1000000007 #define N_MAX 1000000 using namespace std; typedef long long ll; ll modpow(ll a, ll n) { ll ret = 1; while (n) { if (n & 1) { ret = (ret * a) % MOD; } a = (a * a) % MOD; n >>= 1; } return ret; } ll modinv(ll a) { return modpow(a, MOD - 2); } int main(void) { ll *factorial = new ll [N_MAX + 1]; factorial[0] = 1; for (int i = 1; i <= N_MAX; i++) { factorial[i] = (i * factorial[i - 1]) % MOD; } int T; cin >> T; getchar(); while (T--) { char c, dummy; int N, K; ll ret; scanf("%c%c%d%c%d%c%c", &c, &dummy, &N, &dummy, &K, &dummy, &dummy); if (c == 'H') { N = max(0, N + K - 1); } if (K <= N) { ret = factorial[N] * modinv(factorial[N - K]) % MOD; if (c != 'P') { ret = (ret * modinv(factorial[K])) % MOD; } } else { ret = 0; } printf("%lld\n", ret); } return 0; }