比赛 26暑假集训模拟赛3 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 Moo Decomposition 最终得分 100
用户昵称 123 运行时间 0.918 s
代码语言 C++ 内存使用 20.09 MiB
提交时间 2026-07-06 08:44:38
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,mod=1e9+7;
int n,k;
long long l,f[N],inv[N];
string s;
long long qpow(long long x,long long y)
{
    long long ans=1,cnt=x;
    while (y)
    {
        if (y%2==1) ans=ans*cnt%mod;
        cnt=cnt*cnt%mod;
        y/=2;
    }
    return ans;
}
void init()
{
    f[1]=inv[0]=1;
    for (int i=2;i<=N-10;i++) f[i]=f[i-1]*i%mod;
    inv[N-10]=qpow(f[N-10],mod-2);
    for (int i=N-11;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
long long C(int x,int y)
{
    return f[y]*inv[y-x]%mod*inv[x]%mod;
}
void solve()
{
    cin>>k>>n>>l>>s;s=' '+s; 
    int cnt1=0,cnt2=0;
    for (int i=1;i<=n;i++)
    {
        if (s[i]=='M') cnt1++;
        else
        {
            cnt2++;
            if (cnt2>cnt1*k)
            {
                cout<<0;
                return ;
            }
        }
    }
    if ((cnt1+cnt2)%(k+1)!=0) return ;
    long long ans=1;
    int cnt=0;
    for (int i=n;i>=1;i--)
    {
        if (s[i]=='O') cnt++;
        else
        {
            ans=ans*C(k,cnt)%mod,cnt-=k;
        }
    }
    cout<<qpow(ans,l);
}
int main() {
    freopen("Moo.in","r",stdin);
    freopen("Moo.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    init();
    solve();
    return 0;
}