Moo Decomposition

문제

You have a long string $SS$ of Ms and Os and an integer $K\ge 1K\; \backslash geq\; 1$. Count the number of ways of ways to decompose $SS$ into subsequences such that each subsequence is MOOOO....O with exactly $KK$ Os, modulo ${10}^9+710^9+7$.

Since the string is very long, you are not given it explicitly. Instead, you are given an integer $LL$ ($1\le L\le {10}^{18}1\; \backslash leq\; L\; \backslash leq\; 10^\{18\}$), and a string $TT$ of length $NN$ ($1\le N\le {10}^{6}1\; \backslash leq\; N\; \backslash leq\; 10^6$). The string $SS$ is the concatenation of $LL$ copies of the string $TT$.

입력

The first line contains $KK$, $NN$, and $LL$.

The second line contains the string $TT$ of length $NN$. Every character is either an M or an O.

It is guaranteed that the number of decompositions of $SS$ is nonzero.

출력

Output the number of decompositions of string $SS$, modulo ${10}^9+710^9+7$.