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
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
