比赛 26暑假集训模拟赛3 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 Moo Decomposition 最终得分 100
用户昵称 Ruyi 运行时间 1.364 s
代码语言 C++ 内存使用 19.47 MiB
提交时间 2026-07-06 09:37:54
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
#define N 1000001
#define mod 1000000007
using namespace std;
ll k,n,l,ans=1,b[N],c[N],cnt;
bool flag=false;
string t;
ll qpow(ll x,ll y){
    ll res=1;
    while(y>0){
        if(y%2) res=res*x%mod;
        y/=2;
        x=x*x%mod;
    }
    return res;
}
ll C(ll x,ll y){return c[y]*b[x]%mod*b[y-x]%mod;}
int main(){
    freopen("Moo.in","r",stdin);
    freopen("Moo.out","w",stdout);
    cin>>k>>n>>l>>t;
	c[0]=1;
	for(int i=1;i<N;i++) c[i]=c[i-1]*i%mod;
	b[N-1]=qpow(c[N-1],mod-2);
	for(int i=N-2;i>=0;i--) b[i]=b[i+1]*(i+1)%mod;
    //for(int i=1;i<N;i++) cout<<c[i]<<' ';
    //cout<<endl;
    for(int i=n-1;i>=0;i--){
        if(t[i]=='O') cnt++;
        else{
            //cout<<cnt<<' '<<c[cnt]<<endl;
            ans=ans*C(k,cnt)%mod;
            cnt-=k;
        }
    }
    cout<<qpow(ans,l)<<endl;
    return 0;
}