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$ 取模。

输入输出样例 #1

输入 #1

2 6 1
MOOMOO

输出 #1

1

输入输出样例 #2

输入 #2

2 6 1
MMOOOO

输出 #2

6

输入输出样例 #3

输入 #3

1 4 2
MMOO

输出 #3

4

输入输出样例 #4

输入 #4

1 4 100
MMOO

输出 #4

976371285

说明/提示

样例一解释：唯一分解方式是将前三个字符组成一个 $\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$：无额外限制。