gold_Moo_Decomposition — USACO US_Open_Contest
Task type: batch | Time limit: 2 s | Memory limit: 256 MB | Difficulty: 17
Algorithms: number theory, mathematics, fast exponentiation, extended euclidean, combinatorics, prefix sum, modular arithmetic

You have a long string $S$ of Ms and Os and an integer $K \geq 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 $10^9+7$.
Since the string is very long, you are not given it explicitly. Instead, you are
given an integer $L$ ($1 \leq L \leq 10^{18}$), and a string $T$ of length $N$
($1 \leq N \leq 10^6$). 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 $10^9+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 $10^9+7$.
SCORING:
Inputs 5-7: $K=1$, $L = 1$
Inputs 8-10: $K=2$, $N\leq 1000$, $L = 1$
Inputs 11-13: $K=1$
Inputs 14-19: $L = 1$
Inputs 20-25: No additional constraints.
Problem credits: Dhruv Rohatgi

Starter code: