Moo Decomposition timer 1s memory 1024MB

Bessie는 Ms와 Os로 구성된 긴 문자열 S와 정수 K (K ≥ 1)를 받습니다. 문제는 S를 분해하여, 각 분해된 부분 수열이 "MOOO...O"의 형태를 가지도록 하는 방법의 수를 구하는 것입니다. 단, 각 부분 수열은 M 뒤에 정확히 K개의 O로 구성되어야 합니다. 답은 10^9+7로 나눈 나머지를 출력합니다.

문자열 S는 직접 주어지지 않고, 대신 정수 L (1 ≤ L ≤ 10^{18})과 길이 N (1 ≤ N ≤ 10^6)인 문자열 T가 주어집니다. 문자열 S는 문자열 T의 L개의 복사본을 이어 붙여서 만듭니다.