P12028 [USACO25OPEN] Moo Decomposition G

给定一个由 $\texttt{M}$ 和 $\texttt{O}$ 组成的长字符串 $S$ 和一个整数 $K \geq 1$。计算将 $S$ 分解为若干子序列的方式数，其中每个子序列形如 $\texttt{MOOO...O}$（恰好包含 $K$ 个 $\texttt{O}$），结果对 $10^9+7$ 取模。 由于字符串非常长，我们不直接给出 $S$。而是给定一个整数 $L$（$1 \leq L \leq 10^{18}$）和一个长度为 $N$ 的字符串 $T$（$1 \leq N \leq 10^6$）。字符串 $S$ 是 $T$ 重复 $L$ 次拼接而成。

第一行包含 $K$、$N$ 和 $L$。 第二行包含长度为 $N$ 的字符串 $T$，每个字符是 $\texttt{M}$ 或 $\texttt{O}$。 保证 $S$ 的分解方式数不为零。

输出字符串 $S$ 的分解方式数，对 $10^9+7$ 取模。

样例一解释：唯一分解方式是将前三个字符组成一个 $\texttt{MOO}$，后三个字符组成另一个 $\texttt{MOO}$。 样例二解释：共有六种不同的分解方式（大写字母组成一个 $\texttt{MOO}$，小写字母组成另一个 $\texttt{MOO}$）： 1. $\texttt{MmOOoo}$ 2. $\texttt{MmOoOo}$ 3. $\texttt{MmOooO}$ 4. $\texttt{MmoOOo}$ 5. $\texttt{MmoOoO}$ 6. $\texttt{MmooOO}$ 样例四解释：注意：结果需对 $10^9+7$ 取模。 - 测试点 $5\sim7$：$K=1$，$L=1$。 - 测试点 $8\sim10$：$K=2$，$N \leq 1000$，$L=1$。 - 测试点 $11\sim13$：$K=1$。 - 测试点 $14\sim19$：$L=1$。 - 测试点 $20\sim25$：无额外限制。