06775. USACO·哞分解 未做

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

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

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

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

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

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

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

【样例解释】

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

• 测试点 8-10：$K=2$，$N\le 1000$，$L=1$。

• 测试点 11-13：$K=1$。

• 测试点 14-19：$L=1$。

• 测试点 20-25：没有额外限制。

【数据规模与约定】

• 测试点 5-7：$K=1$，$L=1$。

• 测试点 8-10：$K=2$，$N\le 1000$，$L=1$。

• 测试点 11-13：$K=1$。

• 测试点 14-19：$L=1$。

• 测试点 20-25：没有额外限制。

供题：Dhruv Rohatgi