Coin Flipping Sequences

There is a row of N coins on a table. Initially, all coins show heads (H). In each move, exactly M distinct coins are flipped (i.e. their face changes from H to tails (T) or vice versa). After performing exactly K moves, the coins end up in a configuration given by a string S of length N (each character is either H or T).

Let the initial state be all heads. For each coin, a flip changes its state so that its final state is determined by whether it was flipped an even or odd number of times. In other words, a coin will be tails in the end if and only if it is flipped an odd number of times.

Your task is to count the number of sequences of moves (where the order of moves matters) such that, starting from all heads, after exactly K moves the coin configuration becomes exactly S. Since the answer can be huge, output it modulo \(10^9+7\).

Note: In each move, you must choose exactly M distinct coins to flip.

Mathematical formulation:

Define the desired final parity vector \(d = (d_1, d_2, \dots, d_N)\) where \(d_i = 1\) if the i-th coin is tails and \(d_i = 0\) if it is heads. A coin will be tails if and only if it is flipped an odd number of times. Let \(x\) be the number of tails in S (i.e. \(x = \sum_{i=1}^{N} d_i\)).

You need to count the number of sequences of \(K\) moves (each move is an \(N\)-dimensional 0-1 vector with exactly \(M\) ones) whose componentwise sum modulo 2 equals \(d\). Output the count modulo \(10^9+7\).

Input format: The first line contains three integers N, M, and K. The second line contains a string S of length N made up of characters H and T representing the final configuration.

inputFormat

The first line contains three integers N, M, and K separated by spaces.

The second line contains a string S of length N which consists of characters H and T.

Constraints: It is guaranteed that the input is valid.

outputFormat

Output a single integer, which is the number of valid sequences of moves that transform the initial configuration (all H) into S after exactly K moves, taken modulo \(10^9+7\).

sample

3 2 1
TTH

3