Moo Decomposition
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.
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.
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
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
Source: USA Computing Olympiad.
Input Format
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
Output the number of decompositions of string S, modulo 109+7.