记录编号	600050	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[USACO25 Open Gold]Moo Decomposition	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	1.472 s
提交时间	2025-04-12 16:02:17	内存使用	7.63 MiB

#include <cstdio>
typedef long long ll;

const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;

ll kasumi(ll x, ll y) {
	ll res = 1;
	while (y) {
		if (y & 1) res = res * x % MOD;
		y >>= 1;
		x = x * x % MOD;
	}
	return res;
}

int k, n; ll l;
char str[MAXN];
ll fac[MAXN];
ll ans = 1;

ll C(int n, int m) {
	return fac[n] * kasumi(fac[n - m], MOD - 2) % MOD * kasumi(fac[m], MOD - 2) % MOD;
}

int main() {
	freopen("Moo.in", "r", stdin);
	freopen("Moo.out", "w", stdout);
	scanf("%d %d %lld", &k, &n, &l);
	scanf("%s", str + 1);
	
	fac[0] = fac[1] = 1;
	for (int i = 2; i <= n; ++i) fac[i] = i * fac[i - 1] % MOD;
	int ocnt = 0;
	for (int i = n; i >= 1; --i) {
		if (str[i] == 'O') {
			ocnt++;
		} else {
			ans = ans * C(ocnt, k) % MOD;
			ocnt -= k;
		}
	}
	
	printf("%lld", kasumi(ans, l));
	return 0;
}