比赛 |
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;
}