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