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