0pts 编译器上样例全对

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int N = 1e6 + 10;
int jc[N] = {1};
char s[N];
int fffk(int a,int b)
{if(b==1) return a;
	int k=fffk(a,b/2);
	if((b&1)==0){
		return k*k%mod;
	}
	return k*k%mod*a%mod;
}
//CBA
int zhs(int a,int b) {   
	return (jc[b]*fffk(jc[b-a],mod-2)%mod)*fffk(jc[a],mod-2)%mod;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int k,n,l,ans = 1,cnt = 0;
	for(int i=1;i<=n;i++){
		jc[i]=jc[i-1]*i%mod;
	}

	cin>>k>>n>>l;
	cin>>s;
	
	for(int i=n-1;i>=0;i--){
		if(s[i]=='M'){
		   ans=ans*(zhs(k,cnt-(n-i-1-cnt)*k))%mod;
	    }else{
			cnt++;
	    }
	}
	cout<<fffk(ans,l);
}