Subsequence Decomposition into MOO Sequences

We are given an integer (L) (with (1 \le L \le 10^{18})), an integer (K \ge 1), and a string (T) of length (N) (with (1 \le N \le 10^6)) consisting only of the characters M and O. Define a long string (S) to be the concatenation of (L) copies of (T) (i.e. (S = T \Vert T \Vert \cdots \Vert T)).

We say that a sequence of indices forms a valid subsequence if the characters at those indices (taken in increasing order) form a string of the form [ M\underbrace{O O \cdots O}_{K}, , ] that is, one (M) followed by exactly (K) copies of (O).

A decomposition of (S) is a partition of all characters (i.e. every character of (S) is used exactly once) into some number of subsequences, each of which is valid (i.e. has the pattern (M O\cdots O) with exactly (K) copies of (O)).

It is easy to check that such a partition is possible if and only if the total number of (O)'s equals (K) times the total number of (M)'s in (S). In other words, if we let [ M_{\text{total}} = \text{number of } M \text{ in } S \quad\text{and}\quad O_{\text{total}} = \text{number of } O \text{ in } S, ] then a necessary (and in fact sufficient) condition for a valid decomposition is [ O_{\text{total}} = K \cdot M_{\text{total}}. ]

The number of ways to decompose (S) can be computed by processing the characters of (S) from left to right. In a valid decomposition the choices occur only when assigning an (O) to an already started subsequence. More precisely, imagine that each time an (M) is encountered, a new subsequence (group) is started which will eventually need exactly (K) copies of (O) to complete it. Each time an (O) is processed, if there are currently some incomplete groups then one must choose one of these groups to assign the (O) to (the order within the subsequence is fixed, so the only freedom is in choosing which group receives that (O)). However, note that when a group receives its (K\text{-th}) (O) it becomes complete and is no longer available.

A simple way to count the number of decompositions is to simulate the following process on (S):

• Let a variable (s = 0) denote the number of available (incomplete) groups (each group is waiting for some number of (O)'s). Initialize (s = 0) and an answer accumulator (f = 1).
• Process (S) character–by–character (from left to right). For every character:
  • If the character is M, then a new group is started. Increase (s) by (K) (think of this as the group having (K) "slots" for (O)’s that eventually must be filled).
  • If the character is O, then one of the available slots must be used. Multiply (f) by (s) (the number of available slots), and then decrease (s) by (1) (i.e. one slot is filled).

Because (S) is just (L) copies of (T), and because a necessary and sufficient condition for a valid decomposition is that the string (T) itself is balanced (i.e. the number of (O)’s in (T) equals (K) times the number of (M)’s in (T)), the final answer is [ \text{answer} = f^L \pmod{10^9+7}, ] where (f) is the product obtained by processing one copy of (T) with the above procedure starting with (s = 0). (If the string (T) is not balanced, then no valid decomposition exists and the answer is 0.)

Your task is to compute the final answer modulo (10^9+7).

Note: Please output the answer as a single integer.

inputFormat

The input consists of two lines.

1. The first line contains two space‐separated integers: \(L\) and \(K\) (where \(1 \le L \le 10^{18}\) and \(K \ge 1\)).
2. The second line contains the string \(T\) (with \(1 \le |T| \le 10^6\)) consisting only of the characters M and O.

Note: It is guaranteed that \(T\) will be such that a valid decomposition of \(S\) is possible if and only if the number of O's in \(T\) equals \(K\) times the number of M's in \(T\).

outputFormat

Output a single integer: the number of ways to decompose \(S\) into valid subsequences of the form \(M O \cdots O\) (with exactly \(K\) copies of O), modulo \(10^9+7\).

sample

1 1
MO

1