记录编号	600051	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	4132.[USACO25 Open Gold]Moo Decomposition	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	0.787 s
提交时间	2025-04-12 16:11:26	内存使用	4.58 MiB

#include <iostream>
using namespace std;
#define int long long
 
const int mod = 1e9+7;
int k,n,l,f=1,a=1,o=0; 
string s;

int p_w(int x,int y){
    return y?(p_w(x*x%mod,y/2)*(y&1?x:1))%mod:1;
}

signed main(){
	freopen("Moo.in","r",stdin);
	freopen("Moo.out","w",stdout);
    cin>>k>>n>>l>>s; 
	s=" "+s;

    int i=1;
	while(i<=k){
		f=f*i++%mod;
	}
	f=p_w(f,mod-2);
	
 for(int i=n;i;--i)
        if(s[i]=='O') o++;
        else{
            int c=1;
            int j=o-k+1;
            while(j<=o){
            	c=c*j++%mod;
			}
            a=a*c%mod*f%mod;
            o-=k;
        }
    
    cout<<p_w(a,l);
	return 0;
}