比赛 2025.4.12 评测结果 WAWWWWWWWWWWWWWWWWWWWWWWW
题目名称 Moo Decomposition 最终得分 4
用户昵称 LikableP 运行时间 0.274 s
代码语言 C++ 内存使用 2.23 MiB
提交时间 2025-04-12 09:53:36
显示代码纯文本
#include <cstdio>
#include <cstring>
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 *= x) %= MOD;
		y >>= 1;
		(x *= x) %= MOD;
	}
	return res;
}

ll K, N, L;
char str[MAXN];
int len;
ll ans;

int main() {
	freopen("Moo.in", "r", stdin);
	freopen("Moo.out", "w", stdout);
	scanf("%lld %lld %lld", &K, &N, &L);
	scanf("%s", str + 1);
	
	len = strlen(str + 1);
	int mcnt = 0, ocnt = 0;
	for (int i = 1; i <= len; ++i) {
		if (str[i] == 'M') {
			if (str[i - 1] == 'M') mcnt++;
			else mcnt = 1;
			ocnt = 0;
			continue;
		}
		if (str[i] == 'O') {
			ocnt++;
			if (ocnt >= K) {
				(ans += mcnt) %= MOD;
			}
		}
	}
	printf("%lld", kasumi(ans, L));
	return 0;
}