| 比赛 |
26暑假集训模拟赛3 |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
Moo Decomposition |
最终得分 |
100 |
| 用户昵称 |
彭欣越 |
运行时间 |
1.705 s |
| 代码语言 |
C++ |
内存使用 |
12.43 MiB |
| 提交时间 |
2026-07-06 10:20:47 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010,mod=1e9+7;
int m,n;
ll ans=1,l,f[N];
string s;
ll qpow (ll x,ll v) {
//cout << x <<' '<< v <<endl;
ll sum=1;
while (v) {
//cout << sum <<endl;
if (v&1) {
sum*=x;
sum%=mod;
}
x*=x;
x%=mod;
v>>=1;
}
return sum;
}
ll C(int m,int n) {
return qpow(f[n],mod-2)%mod*qpow(f[m-n],mod-2)%mod*f[m]%mod;
}
int main () {
freopen("Moo.in","r",stdin);
freopen("Moo.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
f[0]=1;
for (int i=1;i<=1000000;i++) f[i]=f[i-1]*i%mod;
cin >> m >> n >> l;
cin >> s;
s=' '+s;
int sum=0;
for (int i=1;i<=n;i++) {
if (s[i]=='M') sum+=m+1;
}
if (sum!=n) {
cout << 1 <<endl;
return 0;
}
int cnt=0;
for (int i=n;i>=1;i--) {
//cout << i <<endl;
if (s[i]=='M') {
if (cnt<m) {
cout << 2 <<endl;
return 0;
}else{
ans=ans*C(cnt,m)%mod;
cnt-=m;
}
}else cnt++;
}
cout << qpow(ans,l);
return 0;
}