給定由 M 和 O 構成的長字串 $S$ 及整數 $K \geq 1$。統計將 $S$ 分解成子序列的方案數，使每個均為 MOOOO....O，恰好含 $K$ 個 O，答案對 $10^9+7$ 取模。

字串很長，因此不直接給出。給定整數 $L$（$1 \leq L \leq 10^{18}$）及長度 $N$（$1 \leq N \leq 10^6$）的字串 $T$。$S$ 是 $L$ 份 $T$ 串接而成。

輸入格式

第一行包含 $K$、$N$、$L$。

第二行包含長度 $N$ 的字串 $T$，每個字元是 M 或 O。

保證 $S$ 的分解方案數非零。

輸出格式

輸出 $S$ 的分解方案數，對 $10^9+7$ 取模。

範例

輸入格式 1

2 6 1
MOOMOO

輸出格式 1

1

說明

將 $S$ 分成 MOO 的唯一方式是前三個字元組成一個 MOO，後三個組成另一個。

輸入格式 2

2 6 1
MMOOOO

輸出格式 2

6

說明

有六種不同的子序列分解（大寫字母組成一個 MOO，小寫字母組成另一個）：

• MmOOoo
• MmOoOo
• MmOooO
• MmoOOo
• MmoOoO
• MmooOO

輸入格式 3

1 4 2
MMOO

輸出格式 3

4

輸入格式 4

1 4 100
MMOO

輸出格式 4

976371285

說明

請務必對 $10^9+7$ 取模。

子任務

• 輸入 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: 無額外限制。

題目署名：Dhruv Rohatgi