比赛 26暑假集训模拟赛3 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 Moo Decomposition 最终得分 100
用户昵称 运行时间 0.690 s
代码语言 C++ 内存使用 14.90 MiB
提交时间 2026-07-06 08:39:44
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX (int)(1e18)

int n,k,l;

string s;

const int N=1e6+10;
const int mod=1e9+7;

int ksm(int x,int y){
    int sum=1;
    while(y){
        if(y&1) sum=sum*x%mod;
        x=x*x%mod,y>>=1;
    }
    return sum;
}

int fact[N],invf[N];

void init(){
    fact[0]=1;
    for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%mod;
    invf[n]=ksm(fact[n],mod-2);
    for(int i=n-1;i>=0;i--) invf[i]=invf[i+1]*(i+1)%mod;
}

int C(int x,int y){
    return fact[x]*invf[y]%mod*invf[x-y]%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>>s;init();
    int sum=0,ans=1;
    for(int i=s.size()-1;i>=0;i--){
        if(s[i]=='O') sum++;
        else ans=ans*C(sum,k)%mod,sum-=k;
    }
    ans=ksm(ans,l);
    cout<<ans<<"\n";
    return 0;
}