比赛 26暑假集训模拟赛3 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 Moo Decomposition 最终得分 100
用户昵称 exil 运行时间 1.170 s
代码语言 C++ 内存使用 11.81 MiB
提交时间 2026-07-06 09:39:16
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int xu[1000005];
int kuai(int x,int l){
    int r=x;
    int ans=1;
    r%=mod;
    while(l!=0){
        if(l%2==1){
            ans*=r;
            ans%=mod;
        }
        r*=r;
        r%=mod;
        l/=2;
    }
    return ans;
}
int C(int x,int y){
    if(x==y)return 1;
    int a=xu[x];
    int b=(xu[y]*xu[x-y])%mod;
    b=kuai(b,mod-2)%mod;
    return (a*b)%mod;
    
    
}
string a;
signed main(){
    
    freopen("Moo.in","r",stdin);
    freopen("Moo.out","w",stdout);
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int k,n,l;
    cin>>k>>n>>l;
    cin>>a;
    int len=a.length();
    int q=0;
    
    ////////////////////////////
    int r=1;
    for(int i = 1;i<=1000005;i++){
        r*=i;
        r%=mod;
        xu[i]=r;
    }
    //////////////////////////////
    
    int m=1;
    for(int i = len-1;i>=0;i--){
        if(a[i]=='O'){
            q++;
        }
        else{
            m*=C(q,k);
            q-=k;
            m%=mod;
        }//if(i<=700000)cout<<i<<" "<<q<<endl;
    }
    cout<<kuai(m,l);
    return 0;
}