Moo Decomposition

시간 제한2초메모리 제한2048 MB

요약

M과 O로 이루어진 거대한 주기 문자열을 M 뒤에 O가 정확히 K개 오는 부분수열들로 분해하는 경우의 수를 10^9+7로 나눈 나머지를 구한다.

난이도: 어려움10점 중 8점
유형: 조합론, 동적 계획법, 수학, 누적 합
정답자: 아직 제출이 없습니다

문제

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$ .

예제4

예제 1
입력
```
2 6 1
MOOMOO
```
예상 출력
```
1
```
예제 2
입력
```
2 6 1
MMOOOO
```
예상 출력
```
6
```
예제 3
입력
```
1 4 2
MMOO
```
예상 출력
```
4
```
예제 4
입력
```
1 4 100
MMOO
```
예상 출력
```
976371285
```