ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#8418

Moo Decomposition 1s 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개의 복사본을 이어 붙여서 만듭니다.


入力

첫 번째 줄에 정수 K, N, L이 공백으로 구분되어 주어집니다.

두 번째 줄에는 길이 N인 문자열 T가 주어집니다. T의 모든 문자는 M 또는 O입니다.


出力

문자열 S의 분해 방법의 수를 10^9+7로 나눈 나머지를 출력합니다.


例題 #1

2 6 1
MOOMOO
1

길이 6인 문자열 T가 "MOOMOO"이고, L = 1이므로 S = "MOOMOO"입니다.

오직 한 가지 분해 방법이 있습니다. 첫 3개의 문자를 사용하여 첫 번째 MOO를 만들고, 나머지 3개의 문자를 사용하여 두 번째 MOO를 만들면 각 부분 수열은 M 그 뒤에 정확히 2개의 O로 구성되어 조건을 만족합니다.


例題 #2

2 6 1
MMOOOO
6

  • MmOOoo

  • MmOoOo

  • MmOooO

  • MmoOOo

  • MmoOoO

  • MmooOO


例題 #3

1 4 2
MMOO
4

例題 #4

1 4 100
MMOO
976371285

10^9+7로 나눈 나머지를 출력하는 것을 잊지 마시오.


出典

USACO 2025 US Open Gold

ログインしないとコードを書けません。