比赛 26暑假集训模拟赛3 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 Moo Decomposition 最终得分 100
用户昵称 ChenBp 运行时间 2.983 s
代码语言 C++ 内存使用 12.33 MiB
提交时间 2026-07-06 08:41:54
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=1e6+6;
const ll mod=1e9+7;
string s;
int a[N];
ll ksm(ll x,ll y){
    x%=mod;
    ll res=1;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int jc[N],ni[N];
int main() {
    freopen("Moo.in","r",stdin);
    freopen("Moo.out","w",stdout);
	ll k,n,l;
	cin>>k>>n>>l>>s;
	s=" "+s;
	jc[0]=ni[0]=1;
	for(ll i=1;i<=n;i++){
	    jc[i]=jc[i-1]*i%mod;
	    ni[i]=ksm(jc[i],mod-2);
    }
	ll ans=1;
	for(int i=n; i>=1; i--) {
	    a[i]=a[i+1];
		if(s[i]=='O') a[i]++;
		else {
            ans*=1ll*jc[a[i]]*ni[k]%mod*ni[a[i]-k]%mod;
//            cout<<jc[a[i]]<<" "<<ni[k]<<" "<<ni[a[i]-k]<<endl;
            ans%=mod;
            a[i]-=k;
		}
	}
//	cout<<ans<<endl;
	ans=ksm(ans,l);
	cout<<ans;
	return 0;
}