USACO 2025 US Open Contest, Gold
Problem 1. Moo Decomposition
Contest has ended.
Log in to allow submissions in analysis mode
You have a long string S of Ms and Os and an integer K≥1. Count the number of ways of ways to decompose S into subsequences such that each subsequence is MOOOO....O with exactly K Os, modulo 109+7.
Since the string is very long, you are not given it explicitly. Instead, you are given an integer L (1≤L≤1018), and a string T of length N (1≤N≤106). The string S is the concatenation of L copies of the string T.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains K, N, and L.The second line contains the string T of length N. Every character is either an M or an O.
It is guaranteed that the number of decompositions of S is nonzero.
OUTPUT FORMAT (print output to the terminal / stdout):
Output the number of decompositions of string S, modulo 109+7.SAMPLE INPUT:
2 6 1 MOOMOO
SAMPLE OUTPUT:
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.
SAMPLE INPUT:
2 6 1 MMOOOO
SAMPLE OUTPUT:
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
SAMPLE INPUT:
1 4 2 MMOO
SAMPLE OUTPUT:
4
SAMPLE INPUT:
1 4 100 MMOO
SAMPLE OUTPUT:
976371285
Make sure to take the answer modulo 109+7.
SCORING:
- Inputs 5-7: K=1, L=1
- Inputs 8-10: K=2, N≤1000, L=1
- Inputs 11-13: K=1
- Inputs 14-19: L=1
- Inputs 20-25: No additional constraints.
Problem credits: Dhruv Rohatgi