M과 O로 이루어진 긴 문자열 \(S\)와 정수 \(K \ge 1\)이 있다. \(S\)를 여러 부분 수열로 분해하려고 한다. 각 부분 수열은 M 하나로 시작하고 그 뒤에 정확히 \(K\)개의 O가 이어지는 MOOOO....O 형태여야 한다.

\(S\)를 이와 같이 분해하는 방법의 수를 \(1,000,000,007\)로 나눈 나머지를 구하여라.

문자열이 매우 길기 때문에 \(S\)는 직접 주어지지 않는다. 대신 정수 \(L\) \((1 \le L \le 1,000,000,000,000,000,000)\)과 길이가 \(N\)인 문자열 \(T\) \((1 \le N \le 1,000,000)\)가 주어진다. 문자열 \(S\)는 문자열 \(T\)를 \(L\)번 이어 붙인 문자열이다.

입력

첫째 줄에 \(K\), \(N\), \(L\)이 주어진다.

둘째 줄에 길이가 \(N\)인 문자열 \(T\)가 주어진다. 모든 문자는 M 또는 O이다.

\(S\)를 조건에 맞게 분해하는 방법이 하나 이상 존재함이 보장된다.

출력

문자열 \(S\)를 조건에 맞게 분해하는 방법의 수를 \(1,000,000,007\)로 나눈 나머지를 출력한다.

예제 입력 1

2 6 1
MOOMOO

예제 출력 1

1

예제 설명 1

\(S\)를 MOO들로 분해하는 유일한 방법은 첫 세 문자가 하나의 MOO를 이루고, 마지막 세 문자가 또 하나의 MOO를 이루도록 하는 것이다.

예제 입력 2

2 6 1
MMOOOO

예제 출력 2

6

예제 설명 2

문자열을 부분 수열들로 분해하는 방법은 다음과 같이 6가지이다. 대문자는 한 MOO를 이루고, 소문자는 다른 MOO를 이룬다.

MmOOoo
MmOoOo
MmOooO
MmoOOo
MmoOoO
MmooOO

예제 입력 3

1 4 2
MMOO

예제 출력 3

4

예제 입력 4

1 4 100
MMOO

예제 출력 4

976371285

예제 설명 4

답을 \(1,000,000,007\)로 나눈 나머지를 출력해야 한다.

출처

USACO 2025 US Open Contest, Gold, Problem 1. Moo Decomposition