比赛 26暑假集训模拟赛3 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 Moo Decomposition 最终得分 100
用户昵称 RpUtl 运行时间 0.636 s
代码语言 C++ 内存使用 15.07 MiB
提交时间 2026-07-06 08:38:49
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
int k, n, rest;
ll fac[N], inv[N], ans, l;
string s;
ll ksm(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1; 
    }
    return res;
}
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);
    for (int i = n; i >= 1; i--) inv[i - 1] = inv[i] * i % mod;
    return;
} 
ll C(ll n, ll m) {
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int 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;
    cin >> s; s = " " + s;
    init(); ans = 1;
    for (int i = n; i >= 1; i--) {
        if (s[i] == 'O') rest++;
        else ans = ans * C(rest, k) % mod, rest -= k;
    }
    cout << ksm(ans, l) << '\n';
    return 0;
}