比赛 26暑假集训模拟赛3 评测结果 AAAAWWWWWWWWWWWWWWWWWWWWW
题目名称 Moo Decomposition 最终得分 16
用户昵称 对立猫猫对立 运行时间 1.247 s
代码语言 C++ 内存使用 19.95 MiB
提交时间 2026-07-06 09:06:45
显示代码纯文本
#include <bits/stdc++.h>
#define MOD 1000000007
#define pii pair<int, int>
#define int long long
using namespace std;
int k, n, l;
int a[1000005];
char ch;
int fact[1000005], invfact[1000005];
int qpow(int a, int b) {
    int r = 1;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}
int C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
}
signed main() {
	freopen("Moo.in", "r", stdin);
	freopen("Moo.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> k >> n >> l;
	int LIM = n;
	fact[0] = 1;
    for (int i = 1; i <= LIM; i++) fact[i] = fact[i - 1] * i % MOD;
    invfact[LIM] = qpow(fact[LIM], MOD - 2);
    for (int i = LIM; i >= 1; i--) invfact[i - 1] = invfact[i] * i % MOD;
    for(int i = 1; i <= n; i++) {
    	cin >> ch;
    	if(ch == 'M') {
    		a[i] = 1;
    	}
    	else a[i] = 0;
    }
    int ans = 1;
    int cnto = 0;
    for(int i = n; i >= 1; i--) {
    	if(!a[i]) cnto++;
    	else {
    		if(C(cnto, k)) ans *= C(cnto, k), cnto -= k;
    	}
    }
    cout << qpow(ans, l) << endl;
	return 0;
}