比赛 26暑假集训模拟赛3 评测结果 AAAAAAAAAAWWWAAAAAAWWWWWW
题目名称 Moo Decomposition 最终得分 64
用户昵称 2_16鸡扒拌面 运行时间 1.104 s
代码语言 C++ 内存使用 11.68 MiB
提交时间 2026-07-06 08:58:50
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int N=1000010;

int k,n,l,cnt;
ll ans=1;
char c[N];
ll jc[N];

ll ksm(long long a,long long b)
{
    ll res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

ll C(int a,int b)
{
    if(a<0||a>b)return 0;
    return jc[b]*ksm(jc[a],mod-2)%mod*ksm(jc[b-a],mod-2)%mod;
}

int main()
{
    freopen("Moo.in","r",stdin);
    freopen("Moo.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>k>>n>>l>>c+1;
    jc[0]=1;
    for(int i=1;i<=1e6;i++)jc[i]=jc[i-1]*i%mod;
    for(int i=n;i>=1;--i)
    {
        if(c[i]=='M') ans=ans*C(k,cnt-(n-i-cnt)*k)%mod;
        else cnt++;
    }
    cout<<ksm(ans,l)<<"\n";
    return 0;
}