给定由 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