Наталья и Цезарь любят играть в игры, особенно в те, которые придумали сами. Они решили выложить перед собой последовательность стопок монет, по $m$ монет в каждой, причём каждая монета может быть либо синей, либо красной. В свой ход Наталья может выбрать любую синюю монету и убрать её из игры вместе со всеми монетами, находящимися над ней в этой стопке. Аналогично, в свой ход Цезарь может выбрать любую красную монету и убрать её вместе со всеми монетами из той же стопки, которые находятся выше неё. Игроки ходят по очереди, а проигрывает тот, кто не может сделать правильный ход — то есть когда все его монеты уже были ранее удалены из игры.

Зная правила, они должны определить начальное состояние игры — последовательность из $d$ стопок, каждая из которых содержит ровно $m$ монет. Ни Наталья, ни Цезарь не хотят иметь несправедливого преимущества, поэтому они договорились, что последовательность стопок должна быть «справедливой». Последовательность стопок называется справедливой, если при условии, что Наталья и Цезарь играют оптимально, побеждает тот игрок, который не делает первый ход. Таким образом, если первый ход делает Наталья, то при оптимальной стратегии побеждает Цезарь, и наоборот: если начинает Цезарь, то побеждает Наталья.

Пара уже выложила первые $k$ стопок по $m$ монет в каждой. Теперь они размышляют, как дополнить эту последовательность. Они пришли к выводу, что нет смысла иметь в игре более $n$ стопок монет. Помогите им и для каждого числа $d$ из интервала $[k, n]$ определите, сколько существует различных справедливых последовательностей из $d$ стопок по $m$ монет, которые начинаются с уже выложенной ими последовательности. Две последовательности стопок считаются различными, если существуют такие $i \in [1, d]$ и $j \in [1, m]$, что $j$-я монета в $i$-й стопке синяя в одной из последовательностей и красная в другой.

Поскольку эти результаты могут быть очень большими, достаточно вывести их остатки от деления на $10^9 + 7$.

Входные данные

В первой строке стандартного ввода находятся три целых числа $n, m$ и $k$ ($1 \le n \le 32$; $1 \le m \le 24$; $0 \le k \le n$), обозначающие соответственно ограничение на количество стопок, количество монет в каждой стопке и количество уже созданных стопок.

Следующие $k$ строк содержат описания уже установленных стопок; $i$-я из них содержит строку из символов ‘N’ и ‘C’ длиной ровно $m$, которая обозначает цвета монет в $i$-й стопке, начиная снизу. Если $j$-й символ этой строки — ‘N’, то в $i$-й стопке $j$-я монета снизу синяя. В противном случае этот символ — ‘C’, и монета красная.

Выходные данные

В единственной строке вывода должна содержаться последовательность из $n - k + 1$ целых чисел, где $i$-е из них должно быть остатком от деления на $10^9 + 7$ количества способов, которыми можно удлинить последовательность на $i - 1$ стопку так, чтобы итоговая последовательность стопок была справедливой.

Примеры

Пример 1

3 3 1
CCN

0 1 3

Пример 2

2 1 0

1 0 2

Пример 3

4 2 4
CN
NC
CC
NN

1

Примечание

В первом примере, если мы не добавим никаких стопок, последовательность из одного элемента не будет справедливой. Однако мы можем добавить стопку NNC — такая последовательность из двух стопок уже будет справедливой. Две стопки мы можем добавить тремя способами: [CCN, NNN], [NNN, CCN], [NCN, NCN].

Подзадачи

• В некоторых группах тестов выполняется условие $k = n$.
• В некоторых группах тестов выполняются условия $n \le 8$ и $m \le 8$.
• В niektórych группах тестов выполняются условия $n \le 12$ и $m \le 13$.
• В некоторых группах тестов выполняется условие $n \le 16$ и $m \le 19$.

Каждый вышеперечисленный случай описывает как минимум одну группу, не упомянутую в предыдущих случаях.