레이팅 미적용M과 O로 이루어진 긴 문자열 \(S\)와 정수 \(K \geq 1\)이 주어진다. \(S\)를 부분 수열들로 분해하되, 각 부분 수열이 정확히 \(K\)개의 O를 가진 MOOOO....O 형태가 되도록 하는 방법의 수를 \(10^9+7\)로 나눈 나머지를 구하라.
문자열이 매우 길기 때문에, 문자열이 직접 주어지지는 않는다. 대신 정수 \(L\) (\(1 \leq L \leq 10^{18}\))과 길이 \(N\) (\(1 \leq N \leq 10^6\))의 문자열 \(T\)가 주어진다. 문자열 \(S\)는 문자열 \(T\)를 \(L\)번 이어 붙인 것이다.
Problem credits: Dhruv Rohatgi
SCORING
- 입력 5-7: \(K=1\), \(L = 1\)
- 입력 8-10: \(K=2\), \(N\leq 1000\), \(L = 1\)
- 입력 11-13: \(K=1\)
- 입력 14-19: \(L = 1\)
- 입력 20-25: 추가 제약 없음.
Problem credits: Dhruv Rohatgi
첫째 줄에 \(K\), \(N\), \(L\)이 주어진다.
둘째 줄에 길이 \(N\)의 문자열 \(T\)가 주어진다. 모든 문자는 M 또는 O이다.
\(S\)의 분해 방법의 수가 0이 아님이 보장된다.
문자열 \(S\)의 분해 방법의 수를 \(10^9+7\)로 나눈 나머지를 출력한다.
2 6 1
MOOMOO1The 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
MMOOOO6There 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
1 4 2
MMOO41 4 100
MMOO976371285Make sure to take the answer modulo \(10^9+7\).