其實從前往后做也是可以的。

解析

先不考慮 \(L\)。

一個很自然的想法是從前往后讓每個 \(\texttt{O}\) 跟一個在它前面的 \(\texttt{M}\) 配對。問題在于 \(K\) 的限制難以滿足。

所以先滿足 \(K\) 的限制，對于每個 \(\texttt{M}\)，在它后面預(yù)留 \(K\) 個空位用來放 \(\texttt{O}\)。這樣對于每個 \(\texttt{O}\)，只需要隨便找一個在它前面的 \(\texttt{M}\) 的一個空位放進去就好，這一步的方案數(shù)就是當(dāng)前空位個數(shù)，利用乘法原理就可以求出總方案數(shù)。

但是我們發(fā)現(xiàn)這樣放的話 \(\texttt{O}\) 的順序是亂的，實際上 \(\texttt{O}\) 的順序應(yīng)該是按照其在 \(S\) 中的位置來排的，所以對于每個 \(\texttt{M}\)，需要除一個排列數(shù)。

然后來考慮 \(L\)。

如果 \(T\) 無解，要么是當(dāng)前的 \(\texttt{O}\) 找不到一個合適的 \(\texttt{M}\) 匹配，要么是 \(\texttt{O}\) 不夠拿來匹配。對于前者，不管后面拼多少個 \(T\) 都匹配不了前面的 \(\texttt{O}\)；對于后者，不管后面拼多少個 \(T\) 都拿不出多余的 \(\texttt{O}\)。也就是說，一個無解的 \(T\)，不管拼接多少次，它都是無解的。

如果 \(T\) 有解，考慮拼接后前一段的 \(\texttt{M}\) 會不會匹配上后一段的 \(\texttt{O}\)，答案是不會，因為這樣的話前一段就會有 \(\texttt{O}\) 匹配不上了。

綜上，每一段對答案做的貢獻是獨立且相同的，最終要求的答案就是單段方案數(shù)的 \(L\) 次冪。

代碼

#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;
}