Let's first suppose that $L=1$. As a first attempt, consider some sort of dynamic programming where for each index $i \leq N$, we count the number of ways to validly partition the first $i$ letters of the input string (i.e. the number of partitions so that each subsequence is a string $MO\cdots O$ with at most $k$ $O$'s). If we could compute this for all $i$, then the value for $i = N$ would be our answer. Unfortunately, it's not immediately obvious how to use the value at $i$ to help compute the value at $i+1$, since if the letter at index $i+1$ is an $O$, then for any valid partition of the first $i$ letters, the number of ways to assign the new letter to an existing subsequence depends on how many of these subsequence have strictly less than $k$ $O$'s, which could vary based on the partition. We could try to augment the dynamic programming state with this information (e.g. for each $m$, count the number of valid partitions where exactly $m$ subsequences have less than $k$ $O$'s), but computing these dynamic programming values would seem to require yet more information. We are looking for a roughly linear-time solution, so this approach does not seem promising.

Intuitively, the difficulty arises because for any particular prefix, each $M$ that we have seen so far can be in any of $k+1$ different "states", depending on how many $O$'s have been assigned to it so far, and this affects the combinatorics of the unseen suffix, so the dynamic programming state in a forward-pass algorithm seemingly must include a histogram of how many $M$'s are in each state. This suggests reversing our perspective. In a back-to-front algorithm, where we count the number of valid partitions of each suffix, each $O$ can only be in one of two states (assigned to an $M$, or not), so intuitively all that we need to update our counts is the number of unassigned $O$'s in the suffix. Moreover, this is always the total number of $O$'s in the suffix, minus $k$ times the total number of $M$'s in the suffix, irrespective of the partition!

More formally, suppose we have computed $V_i$, the number of ways to partition the last $i$ letters so that all but one subsequence are strings $MO\cdots O$ with exactly $k$ $O$'s, and the remaining subsequence is the unused $O$'s. To compute $V_{i+1}$ there are two cases. If the $i+1$-st letter from the end is an $O$, then $V_{i+1} = V_i$ since this letter cannot be used yet. Otherwise, $V_{i+1} = \binom{O_i - kM_i}{k} V_i$, since for each valid partition of the last $i$ letters, there are $\binom{O_i - kM_i}{k}$ ways to choose $k$ $O$'s from the unused $O$'s. Here, $O_i$ is the number of $O$'s in the last $i$ letters, and $M_i = i-O_i$ is the number of $M$'s in the last $i$ letters. This gives an $O(N)$ time algorithm so long as we can efficiently compute the needed binomial coefficients. While this algorithm is most naturally expressed via a reverse pass through the input data, it can just as easily be implemented in a forward pass by maintaining the value $O_i - kM_i$; see the code below.

There are several ways to compute the needed binomial coefficients efficiently. One way, which suffices for this problem, is to precompute all factorials up to $N!$ (all modulo $p = 10^9 + 7$). We can then compute any given binomial coefficient $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ efficiently by using Fermat's little theorem for the modular inverses: $a^{p-2} \equiv a^{-1} \bmod{p}$ for any $1\leq a < p$ and prime $p$. Since $p$ is large, we need to use fast exponentiation (i.e. repeated squaring) to compute the quantities $a^{p-2} \bmod{p}$.

This is a complete solution for $L=1$. To extend to general $L$, it suffices to notice that no subsequence can cross between two different repeats of the input string: for example, if some subsequence starting in the second-to-last repeat used an $O$ in the last repeat, then the last repeat would not have enough $O$'s for all of its $M$'s; this argument generalizes. Thus, the answer for general $L$ is equal to the answer for $L=1$, raised to the $L$-th power. We can compute this quantity using fast exponentiation.

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define MOD 1000000007
#define MAXN 1000001
 
int fact[MAXN];
 
int mul(int a, int b) { return (((long long)a) * b) % MOD; }
 
void computeFactorials() {
	fact[0] = 1;
	for (int i = 1; i <= MAXN; i++) fact[i] = mul(fact[i - 1], i);
}
 
int bexp(int a, long long e) {
	if (e == 0) return 1;
	int ans = bexp(a, e / 2);
	ans = mul(ans, ans);
	if (e % 2) ans = mul(ans, a);
	return ans;
}
 
int binv(int a) { return bexp(a, MOD - 2); }
 
int binom(int n, int k) {
	int ans = fact[n];
	ans = mul(ans, binv(fact[k]));
	ans = mul(ans, binv(fact[n - k]));
	return ans;
}
 
int main() {
	int N, K;
	long long L;
	cin >> K >> N >> L;
	computeFactorials();
	string s;
	cin >> s;
	int req = 0;
	int ans = 1;
	for (int i = 0; i < N; i++) {
		if (s[i] == 'M') {
			ans = mul(ans, binom(req + K, K));
			req += K;
		} else req--;
	}
	cout << bexp(ans, L) << '\n';
}