#PU1521. USACO 2025 US Open Contest, Gold — Problem 1. Moo Decomposition
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 of Ms and Os and an integer . Count the number of ways of ways to decompose into subsequences such that each subsequence is MOOOO....O with exactly Os, modulo . Since the string is very long, you are not given it explicitly. Instead, you are given an integer (), and a string of length (). The string is the concatenation of copies of the string .
输入格式
The first line contains , , and . The second line contains the string of length . Every character is either an M or an O. It is guaranteed that the number of decompositions of is nonzero.
输出格式
(见题面原文)
数据范围
Inputs 5-7: , Inputs 8-10: , , Inputs 11-13: Inputs 14-19: 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$.