Moo Decomposition

题目描述

给定一个由字符 M 和 O 组成的长字符串 $S$，以及整数 $K \geq 1$。请统计将 $S$ 分解为若干个子序列的方案数，使得每个子序列都形如 MOOOO....O（恰好包含 $K$ 个 O），并对 $10^9+7$ 取模。

由于字符串非常长，你不会被直接给出 $S$。相反，给定一个整数 $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

2 6 1
MMOOOO

6

1 4 2
MMOO

4

1 4 100
MMOO

976371285

提示

将 $S$ 分解为 MOOs 的唯一方式是让前三个字符构成一个 MOO，后三个字符构成另一个 MOO。

将该字符串分解为子序列共有六种不同方式（大写字母构成一个 MOO，小写字母构成另一个）： MmOOoo MmOoOo MmOooO MmoOOo MmoOoO MmooOO

请确保对答案取模 $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

标签: USACO|2025|Gold

来源

USACO|2025|Gold