#include<cstdio>
#include<cstring>
#include<cctype>
#define rep(i,a) for(int i=0;i<(a);++i)

typedef long long ll;

const ll mod = 1000000007;

int T;

ll fact[1000001];

ll extgcd( ll a, ll b, ll &x, ll &y )
{
	int d = b;

	if( b )
	{
		d = extgcd( b, a%b, y, x );
		y -= a/b*x;
	}
	else
		x = 1, y = 0;

	return d;
}

ll divMod( ll a, ll b, ll m )
{
	ll x, y;
	extgcd( b, m, x, y );

	return ((a*x)%m+m)%m;
}

ll perm( int n, int r )
{ return n<r?0:divMod( fact[n], fact[n-r], mod ); }

ll comb( int n, int r )
{ return n<r?0:divMod( perm(n,r), fact[r], mod ); }

ll homo( int n, int r )
{ return comb( n+r-1, r ); }

int read( char S[], int &p )
{
	int q = 0, len = strlen(S);

	while( p < len && isdigit( S[p] ) )
	{
		q *= 10;
		q += S[p]-'0';
		++p;
	}

	return q;
}

int main()
{
	fact[0] = 1;
	rep( i, 1000000 )
		fact[i+1] = (i+1)*fact[i] % mod;

	scanf( "%d", &T );
	rep( i, T )
	{
		char S[21];
		scanf( "%s", S );

		int p = 2;
		int n = read(S, p), r = read(S, ++p);

		printf( "%lld\n", (*S=='C'?comb:*S=='P'?perm:homo)(n, r) );
	}

	return 0;
}