| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 88 | 48 | 40 | 58.824% |
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$.
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 the number of decompositions of string $S,ドル modulo 10ドル^9+7$.
2 6 1 MOOMOO
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.
2 6 1 MMOOOO
6
There are six distinct ways to decompose the string into subsequences (uppercase letters form one MOO, lowercase letters form another):
1 4 2 MMOO
4
1 4 100 MMOO
976371285
Make sure to take the answer modulo 10ドル^9+7$.