#PU1521. USACO 2025 US Open Contest, Gold — Problem 1. Moo Decomposition

    ID: 1675 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:open25来源:usaco.orgscoring:equal_test_cases组合数学

USACO 2025 US Open Contest, Gold — Problem 1. Moo Decomposition

USACO 2025 US Open Contest, Gold — Problem 1. Moo Decomposition

题目描述

You have a long string SS of Ms and Os and an integer K≥1K \geq 1. Count the number of ways of ways to decompose SS into subsequences such that each subsequence is MOOOO....O with exactly KK Os, modulo 109+710^9+7. Since the string is very long, you are not given it explicitly. Instead, you are given an integer LL (1≤L≤10181 \leq L \leq 10^{18}), and a string TT of length NN (1≤N≤1061 \leq N \leq 10^6). The string SS is the concatenation of LL copies of the string TT.

输入格式

The first line contains KK, NN, and LL. The second line contains the string TT of length NN. Every character is either an M or an O. It is guaranteed that the number of decompositions of SS is nonzero.

输出格式

(见题面原文)

数据范围

Inputs 5-7: K=1K=1, L=1L = 1 Inputs 8-10: K=2K=2, N≤1000N\leq 1000, L=1L = 1 Inputs 11-13: K=1K=1 Inputs 14-19: L=1L = 1 Inputs 20-25: No additional constraints. Problem credits: Dhruv Rohatgi

样例

样例 1

2 6 1
MOOMOO
1
The only way to decompose $S$ into MOOs is to let the first three characters form a MOO and
the last three characters form another MOO.

样例 2

2 6 1
MMOOOO
6
There are six distinct ways to decompose the string into subsequences (uppercase
letters form one MOO, lowercase letters form another):
MmOOoo
MmOoOo
MmOooO
MmoOOo
MmoOoO
MmooOO

样例 3

1 4 2
MMOO
4

样例 4

1 4 100
MMOO
976371285
Make sure to take the answer modulo $10^9+7$.