Problem 1. Moo Decomposition

USACO 2025 US Open Contest, Gold

你有一个由字符 M 和 O 组成的长字符串 $S$ 和一个整数 $K \geq 1$。计算将 $S$ 分解为子序列的方案数，使得每一个子序列均为 MOOOO....O，其中恰有 $K$ 个 O，答案对 $10^9+7$ 取模。

由于字符串非常长，其未被直接给出。你被给定一个整数 $L$（$1 \leq L \leq 10^{18}$）和一个长为 $N$ 的字符串 $T$（$1 \leq N \leq 10^6$）。字符串 $S$ 等于 $L$ 个字符串 $T$ 的拼接。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $K$，$N$ 和 $L$。

第二行包含长为 $N$ 的字符串 $T$。每一个字符均为 M 和 O 之一。

输入保证 $S$ 的分解方案数非零。

输出格式（输出至终端 / 标准输出）：

输出一行，包含字符串 $S$ 的分解方案数，答案对 $10^9+7$ 取模。

输入样例：

2 6 1
MOOMOO

输出样例：

1

将 $S$ 分解为 MOO 的唯一方案是令前三个字符组成一个 MOO，后三个字符组成另一个 MOO。

输入样例：

2 6 1
MMOOOO

输出样例：

6

有六种不同的方案将字符串分解为子序列（大写字母组成一个 MOO，小写字母形成另一个）：

• MmOOoo
• MmOoOo
• MmOooO
• MmoOOo
• MmoOoO
• MmooOO

输入样例：

1 4 2
MMOO

输出样例：

4

输入样例：

1 4 100
MMOO

输出样例：

976371285

确保输出答案对 $10^9+7$ 取模。

测试点性质： 测试点 5-7：$K=1$，$L = 1$。测试点 8-10：$K=2$，$N\leq 1000$，$L = 1$。测试点 11-13：$K=1$。测试点 14-19：$L = 1$。测试点 20-25：没有额外限制。

供题：Dhruv Rohatgi