Problems
Bessie is given a long string S consisting of the characters M and O, along with an integer K (K ≥ 1). The problem is to count the number of ways to decompose S into subsequences such that each subsequence is of the form "MOOO...O" with exactly K O's following an M. The answer should be given modulo 10^9+7.
Since the string S is very long, it is not given explicitly. Instead, you are provided an integer L (1 ≤ L ≤ 10^18) and a string T of length N (1 ≤ N ≤ 10^6). The string S is the concatenation of L copies of the string T.
Input
The first line contains three space-separated integers K, N, and L.
The second line contains the string T of length N. Every character of T is either M or O.
Output
Output a single line containing the number of ways to decompose the string S into subsequences (each of the form M followed by exactly K O's) modulo
Example #1
2 6 1
MOOMOO
1
The only way to decompose
Example #2
2 6 1
MMOOOO
6
MmOOoo
MmOoOo
MmOooO
MmoOOo
MmoOoO
MmooOO
Example #3
1 4 2
MMOO
4
Example #4
1 4 100
MMOO
976371285
Make sure to take the answer modulo
You must sign in to write code.