Natalia 和 Cezary 喜歡玩遊戲，特別是他們自己發明的遊戲。他們決定排出一列硬幣堆，每堆包含 $m$ 枚硬幣，每枚硬幣不是藍色就是紅色。在 Natalia 的回合中，她可以選擇任何一枚藍色硬幣，並將其連同該堆中位於其上方的所有硬幣一起從遊戲中移除。同樣地，在 Cezary 的回合中，他可以選擇任何一枚紅色硬幣，並將其連同該堆中位於其上方的所有硬幣一起從遊戲中移除。玩家輪流進行操作，無法進行合法操作者即為輸家——也就是說，當所有硬幣都已被移除時。

在了解規則後，他們現在必須確定遊戲的初始狀態——一個包含 $d$ 堆硬幣的序列，每堆恰好包含 $m$ 枚硬幣。Natalia 和 Cezary 都不希望對方擁有不公平的優勢，因此他們一致認為硬幣堆序列必須是「公平的」。如果假設 Natalia 和 Cezary 都採取最佳策略，且由後手獲勝，則稱該硬幣堆序列為公平的。也就是說，如果由 Natalia 先手，則在最佳策略下 Cezary 會獲勝；反之亦然：如果由 Cezary 先手，則 Natalia 會獲勝。

這對搭檔已經排好了前 $k$ 堆硬幣，每堆 $m$ 枚。現在他們正在考慮如何完成這個序列。他們已經得出結論，遊戲中不應超過 $n$ 堆硬幣。請幫助他們，對於區間 $[k, n]$ 中的每個數字 $d$，計算有多少種不同的公平序列（包含 $d$ 堆，每堆 $m$ 枚）是以他們已經排好的序列作為開頭的。如果存在 $i \in [1, d]$ 和 $j \in [1, m]$，使得在兩個序列中，第 $i$ 堆的第 $j$ 枚硬幣顏色不同（一個為藍色，另一個為紅色），則稱這兩個序列不同。

由於結果可能非常大，請輸出它們對 $10^9 + 7$ 取模後的餘數。

輸入格式

第一行包含三個整數 $n, m, k$ ($1 \le n \le 32; 1 \le m \le 24; 0 \le k \le n$)，分別表示硬幣堆數量的上限、每堆硬幣的數量以及已經建立的硬幣堆數量。

接下來的 $k$ 行包含已經設置好的硬幣堆描述；第 $i$ 行包含一個長度恰好為 $m$ 的字串，由 'N' 和 'C' 組成，表示第 $i$ 堆中從底部開始的硬幣顏色。如果字串的第 $j$ 個字元是 'N'，則表示第 $i$ 堆中從底部數起的第 $j$ 枚硬幣是藍色的。否則，該字元為 'C'，表示該硬幣是紅色的。

輸出格式

輸出單行，包含 $n - k + 1$ 個整數，其中第 $i$ 個數應為將序列延長 $i - 1$ 堆，使得最終序列為公平序列的方法數，對 $10^9 + 7$ 取模後的結果。

範例

範例 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$。
• 在某些測試組中，滿足條件 $n \le 12$ 且 $m \le 13$。
• 在某些測試組中，滿足條件 $n \le 16$ 且 $m \le 19$。

上述每個情況至少描述了一組在先前情況中未提及的測試組。