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