其实从前往后做也是可以的。

解析

先不考虑 $L$。

一个很自然的想法是从前往后让每个 $\texttt{O}$ 跟一个在它前面的 $\texttt{M}$ 配对。问题在于 $K$ 的限制难以满足。

所以先满足 $K$ 的限制，对于每个 $\texttt{M}$，在它后面预留 $K$ 个空位用来放 $\texttt{O}$。这样对于每个 $\texttt{O}$，只需要随便找一个在它前面的 $\texttt{M}$ 的一个空位放进去就好，这一步的方案数就是当前空位个数，利用乘法原理就可以求出总方案数。

但是我们发现这样放的话 $\texttt{O}$ 的顺序是乱的，实际上 $\texttt{O}$ 的顺序应该是按照其在 $S$ 中的位置来排的，所以对于每个 $\texttt{M}$，需要除一个排列数。

然后来考虑 $L$。

如果 $T$ 无解，要么是当前的 $\texttt{O}$ 找不到一个合适的 $\texttt{M}$ 匹配，要么是 $\texttt{O}$ 不够拿来匹配。对于前者，不管后面拼多少个 $T$ 都匹配不了前面的 $\texttt{O}$；对于后者，不管后面拼多少个 $T$ 都拿不出多余的 $\texttt{O}$。也就是说，一个无解的 $T$，不管拼接多少次，它都是无解的。

如果 $T$ 有解，考虑拼接后前一段的 $\texttt{M}$ 会不会匹配上后一段的 $\texttt{O}$，答案是不会，因为这样的话前一段就会有 $\texttt{O}$ 匹配不上了。

综上，每一段对答案做的贡献是独立且相同的，最终要求的答案就是单段方案数的 $L$ 次幂。

代码

/* 
先不考虑 L
发现每个 O 只能跟在它前面的 M 匹配 
这个上界很烦啊，怎么处理呢？
现在有的是每 K + 1 位放一个 M
O 只能在间隔的空位里放
空位数量我是知道的
现在问题是按理来说一个 O 只能放在某个 M 第一个空位上，而直接放放的是任意空位上
也就是说实际的排列是定的，是不是除一个排列数就好了？
手玩一下样例
是对的 
再来考虑这个 L 
首先发现原始字符串本身一定能把 O 消耗完，不然到最后 O 的总数不能完全匹配所有的 M
那这就好办了，其实就是原始答案的 L 次幂而已 
怎么不对啊
L 的问题
原来是没开 long long 
*/
#include <bits/stdc++.h>
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
#define mid ((l + r) >> 1)
#define eps 0.000001
using namespace std;
typedef __int128 i128;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,int> pii;
const int N = 1e5 + 5, M = 2e5 + 5,base1 = 13331,base2 = 131,mod = 1e9 + 7;
int qmi(int a,ll b){
	int res = 1;
	while(b){
		if(b & 1) res = 1ll * res * a % mod;
		b >>= 1;
		a = 1ll * a * a % mod;
	}
	return res;
} 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	ll k,n,l;
	cin>>k>>n>>l;
	int fac = 1;
	for(int i=1;i<=k;i++){
		fac = 1ll * i * fac % mod;
	}
	string s;
	cin>>s;
	int now = 0,res = 1,cntm = 0;
	for(int i=0;i<s.size();i++){
		if(s[i] == 'M') now += k,cntm++;
		else{
			res = 1ll * res * now % mod;
			now--;
		}
	}
	assert(now == 0);
//	cout<<s.size()<<" "<<res<<" "<<fac<<" "<<cntm<<'\n';
	cout<<qmi(1ll * res * qmi(qmi(fac,cntm),mod - 2) % mod,l);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
const int P=1e9+7;
LL fac[N]; char s[N];
LL ksm(LL a, LL b){
    LL ans=1;
    for(;b;b>>=1,a=a*a%P)if(b&1) ans=ans*a%P;
    return ans;
}
LL calc(int n, int m) {return fac[n]*ksm(fac[m], P-2)%P*ksm(fac[n-m], P-2)%P;}
int main(){
    fac[0]=1; for(int i=1; i<=N-10; i++) fac[i]=fac[i-1]*i%P; 
    int K, n; LL L; scanf("%d%d%lld", &K, &n, &L);
    scanf("%s", s+1);
    LL ans=1,cnt=0;
    for(int i=n; i>=1; i--){
        if(s[i]=='O') cnt++;
        else if(s[i]=='M'){
            ans=ans*calc(cnt, K)%P;
            cnt-=K;
        } 
    }printf("%lld\n", ksm(ans, L));
    return 0;
}