比赛 26暑假集训模拟赛3 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 Moo Decomposition 最终得分 100
用户昵称 KKZH 运行时间 2.769 s
代码语言 C++ 内存使用 14.89 MiB
提交时间 2026-07-06 10:10:15
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
const int mod=1e9+7;
int all[N],inv[N];
int k,n,l;
string s;
int ksm(int x,int y){
    int cnt=x,res=1;
	while(y>0){
		if(y%2==1)
			res=(cnt*res)%mod;
		cnt=(cnt*cnt)%mod;
		y=y/2;
	}
	return res;
}
int c(int x,int y){
    if(x==y) return 1;
    return (all[y]*inv[y-x])%mod*inv[x]%mod;
}
signed main(){
    freopen("Moo.in","r",stdin);
    freopen("Moo.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>k>>n>>l>>s;
	all[0]=1,inv[0]=1;
	for(int i=1;i<=n;i++){
	    all[i]=(all[i-1]*i)%mod;
	    inv[i]=ksm(all[i],mod-2)%mod;
//	    cout<<all[i]<<" "<<inv[i]<<'\n'; 
	}
	int cnt=0,ans=1;
    for(int i=s.size()-1;i>=0;i--){
        if(s[i]=='O') cnt++;
        else{
            ans=(ans*c(k,cnt)%mod)%mod;
            cnt-=k;
        }
//        cout<<ans<<" ";
    } 
    cout<<ksm(ans,l)<<'\n';
	return 0;
}