ナタリアとツェザリはゲームが好きで、特に自分たちで考えたゲームを好みます。彼らはそれぞれ $m$ 枚のコインからなるコインの山を並べることにしました。各コインは青色か赤色のいずれかです。ナタリアは自分の手番で、任意の青いコインを選び、そのコインと、その山でそのコインの上にあるすべてのコインを取り除くことができます。同様に、ツェザリは自分の手番で、任意の赤いコインを選び、そのコインと、その山でそのコインの上にあるすべてのコインを取り除くことができます。プレイヤーは交互に手番を行い、有効な手番を行えなくなったプレイヤー（つまり、すべてのコインがすでにゲームから取り除かれている状態）が敗北となります。

彼らはゲームの初期状態、すなわちそれぞれがちょうど $m$ 枚のコインを含む $d$ 個の山の列を決定する必要があります。ナタリアもツェザリも不公平な有利さを望まないため、彼らは山の列が「公平」であるべきだと合意しました。山の列が公平であるとは、ナタリアとツェザリが最適にプレイすると仮定したとき、先手ではないプレイヤーが勝利することを指します。つまり、ナタリアが先手であればツェザリが勝利し、ツェザリが先手であればナタリアが勝利するということです。

二人はすでに $m$ 枚のコインからなる最初の $k$ 個の山を並べました。今、彼らはこの山の列をどのように完成させるかを考えています。彼らは、ゲーム内の山の数が $n$ 個を超えても意味がないという結論に達しました。彼らを助けるために、各 $d \in [k, n]$ について、すでに並べられた山から始まる $m$ 枚のコインからなる $d$ 個の山の公平な列が何通り存在するかを求めてください。2つの山の列は、ある $i \in [1, d]$ と $j \in [1, m]$ が存在し、一方の列の $i$ 番目の山の $j$ 番目のコインが青色で、もう一方の列では赤色である場合に異なるとみなされます。

結果は非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを求めてください。

入力

標準入力の最初の行には、3つの整数 $n, m, k$ ($1 \le n \le 32; 1 \le m \le 24; 0 \le k \le n$) が含まれており、それぞれ山の数の上限、各山に含まれるコインの数、すでに作成された山の数を表します。

続く $k$ 行には、すでに設定された山の説明が含まれています。$i$ 番目の行には、下から順にコインの色を表す長さ $m$ の文字列（'N' または 'C'）が含まれています。$j$ 番目の文字が 'N' の場合、$i$ 番目の山の底から $j$ 番目のコインは青色です。そうでない場合、その文字は 'C' であり、コインは赤色です。

出力

出力の唯一の行には、$n - k + 1$ 個の整数が含まれている必要があります。$i$ 番目の整数は、最終的な山の列が公平になるように $i - 1$ 個の山を追加する方法の数を $10^9 + 7$ で割った余りである必要があります。

入出力例

入力 1

3 3 1
CCN

出力 1

0 1 3

入力 2

2 1 0

出力 2

1 0 2

入力 3

4 2 4
CN
NC
CC
NN

出力 3

1

注記

最初の例では、山を追加しない場合、1つの山からなる列は公平ではありません。しかし、NNC という山を追加することはでき、その場合2つの山からなる列は公平になります。2つの山を追加する方法は、[CCN, NNN], [NNN, CCN], [NCN, NCN] の3通りです。

小課題

• $k = n$ を満たすテストグループが存在します。
• $n \le 8$ かつ $m \le 8$ を満たすテストグループが存在します。
• $n \le 12$ かつ $m \le 13$ を満たすテストグループが存在します。
• $n \le 16$ かつ $m \le 19$ を満たすテストグループが存在します。

上記の各ケースは、それ以前のケースで言及されていない少なくとも1つのグループを記述しています。