比赛 2025.4.12 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 Moo Decomposition 最终得分 100
用户昵称 李奇文 运行时间 0.891 s
代码语言 C++ 内存使用 19.08 MiB
提交时间 2025-04-12 10:11:58
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1000000007;
const int N=1000000+5; 
ll k,n,l;
string a;
ll b[N],c[N];
ll lo,ko,ans=1;
ll ksm(ll x,ll y){
	if(!y) return 1ll;
	ll op=ksm(x,y>>1);
	op=op*op%mod;
	if(y&1) op=op*x%mod;
	return op;
}
ll C(ll i,ll j){
	return c[j]*b[i]%mod*b[j-i]%mod;
}
void init(){
	c[0]=1;
	for(int i=1;i<=1000000;i++) c[i]=c[i-1]*i%mod;
	b[1000000]=ksm(c[1000000],1000000005);
	for(int i=999999;i>=0;i--) b[i]=b[i+1]*(i+1)%mod;
	return;
}
int main(){
	freopen("Moo.in","r",stdin);
	freopen("Moo.out","w",stdout);
	ios::sync_with_stdio(0);
	cin>>k>>n>>l>>a;
	init();
	for(ll i=n-1;i>=0;i--){
		if(a[i]=='O'){
			ko++;
		}else{
			ans=ans*C(k,ko)%mod;
			ko-=k;
		}
	}
	cout<<ksm(ans,l);
	return 0;
}