比赛 26暑假集训模拟赛3 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 Moo Decomposition 最终得分 100
用户昵称 rzzakioi 运行时间 3.026 s
代码语言 C++ 内存使用 16.11 MiB
提交时间 2026-07-06 09:08:06
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int k,n,l,a[1000005],cnt,jc[1000005],ny[1000005];
string s;
int fpow(int x,int y){
    int ans=1;
    while(y){
        if(y&1){
            ans*=x;
            ans%=mod;
        }
        x*=x;
        x%=mod;
        y>>=1;
    }
    return ans;
}
int C(int x,int y){
    int ans=jc[x];
    ans*=ny[y];
    ans%=mod;
    ans*=ny[x-y];
    ans%=mod;
    return ans;
}
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>>s;
    s=' '+s;
    jc[0]=1;jc[1]=1;
    for(int i=2;i<=n;i++){
        jc[i]=jc[i-1]*i;
        jc[i]%=mod;
    }
    for(int i=0;i<=n;i++){
        ny[i]=fpow(jc[i],mod-2);
    }
    int res=0;
    for(int i=n;i>=1;i--){
        if(s[i]=='M'){
            a[++cnt]=res;
            res=0;
        }
        else res++;
    }
    for(int i=1;i<=cnt;i++){
        a[i]+=a[i-1];
    }
    int ans=1;
    for(int i=1;i<=cnt;i++){
        ans*=C(a[i]-(i-1)*k,k);
        ans%=mod;
    }
    cout<<fpow(ans,l);
    return 0;
}