比赛 26暑假集训模拟赛3 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 Moo Decomposition 最终得分 100
用户昵称 赵飞羽 运行时间 0.698 s
代码语言 C++ 内存使用 14.91 MiB
提交时间 2026-07-06 09:04:52
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1000010, MOD = 1e9 + 7;
int k, n, l, ans = 1, cnt, fac[N], inv[N];
string s;

int ksm(int x, int y, int p) {
	int res = 1;
	while (y) {
		if (y&1) (res *= x) %= p;
		(x *= x) %= p;
		y >>= 1;
	}
	return res % p;
}

void init() {
	fac[0] = 1;
	for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i % MOD;
	inv[n] = ksm(fac[n], MOD - 2, MOD);
	for (int i = n - 1; i >= 0; i--) inv[i] = inv[i+1] * (i + 1) % MOD;
}

int C(int x, int y) {
	if (y < 0 || x < y) return 0;
	return fac[x] * inv[y] % MOD * inv[x-y] % MOD; 
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	freopen("Moo.in", "r", stdin);
	freopen("Moo.out", "w", stdout);
	cin >> k >> n >> l >> s;
	init();
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] == 'O') ++cnt;
		else {
			(ans *= C(cnt, k)) %= MOD;
			cnt -= k;
			if (cnt < 0) {
				cnt = 0;
				break;
			}
		}
	}
	cout << ksm(cnt? 0: ans, l, MOD);
	return 0;
}