#include #define __dist_rep(a1,a2,a3,f,...) f #define __rep2(i,n) for (int i=0; i<(n); ++i) #define __rep3(i,a,b) for (int i=(a); i<(b); ++i) #define rep(...) __dist_rep(__VA_ARGS__,__rep3,__rep2)(__VA_ARGS__) #define rrep(i,n) for (int i=(n)-1; i>=0; --i) #define fi first #define se second #define debug(x) cerr<<#x<<": "<<(x)< pii; typedef pair pll; typedef vector vi; typedef vector vvi; typedef vector vl; typedef vector vvl; template string tostring(const T &x) { ostringstream oss; oss << x; return oss.str(); } template bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; } const int INF = 1e9+5; const ll LINF = 1LL<<60; const ll MOD = 1e9+7; vector fac, finv, inv; void com_init(int n) { fac.resize(n+1,1); finv.resize(n+1,1); inv.resize(n+1,1); inv[0] = 0; for (int i=2; i<=n; ++i) { fac[i] = fac[i-1]*i % MOD; inv[i] = -inv[MOD%i]*(MOD/i) % MOD + MOD; finv[i] = finv[i-1]*inv[i] % MOD; } } ll com(int n, int k) { if (n>t; com_init(1000000); rep(q,t) { string s; cin>>s; char c=s[0]; int i; for (i=2; i