동전

나탈리아와 체자리는 게임을 즐기는데, 특히 자신들이 직접 만든 게임을 좋아한다. 두 사람은 동전 스택을 여러 개 일렬로 늘어놓기로 했다. 각 스택에는 정확히 $m$개의 동전이 쌓여 있으며, 각 동전은 파란색 또는 빨간색이다. 나탈리아는 자기 차례에 파란색 동전 하나를 고르고, 그 동전과 같은 스택에서 그 위에 있는 모든 동전을 게임에서 제거한다. 체자리는 자기 차례에 빨간색 동전 하나를 고르고, 같은 방식으로 제거한다. 두 사람은 번갈아 가며 수를 두고, 올바른 수를 둘 수 없는 사람이 진다. 올바른 수를 둘 수 없다는 것은 자기 색 동전이 모두 이미 제거되었다는 뜻이다.

두 사람이 최적으로 플레이할 때 첫 수를 두지 않는 사람이 이기는 스택 나열을 공정하다고 한다. 즉 나탈리아가 먼저 두면 체자리가 이기고, 체자리가 먼저 두면 나탈리아가 이긴다.

두 사람은 이미 처음 $k$개의 스택을 각각 $m$개의 동전으로 쌓았고, 이 나열을 어떻게 끝낼지 고민하고 있다. 게임에 스택이 $n$개를 넘을 필요는 없다고 결론지었다. 각 $d \in [k, n]$에 대해, 이미 쌓은 스택들로 시작하고 스택이 $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$인 문자열이며, 아래에서부터 $i$번째 스택의 색을 나타낸다. $j$번째 문자가 'N'이면 아래에서 $j$번째 동전은 파란색이다. 그렇지 않으면 문자는 'C'이고 그 동전은 빨간색이다.

한 줄에 $n - k + 1$개의 정수를 공백으로 구분해 출력한다. $i$번째 수는 스택을 $i - 1$개 덧붙여 최종 나열을 공정하게 만들 수 있는 방법의 수를 $10^9 + 7$로 나눈 나머지다.

첫 번째 예시 설명이다. 스택을 아무것도 더하지 않으면 원소가 하나뿐인 나열은 공정하지 않다. 반면 NNC 스택을 하나 더하면 두 스택으로 이루어진 나열이 공정해진다. 두 스택을 더하는 방법은 세 가지다. [CCN, NNN], [NNN, CCN], [NCN, NCN]이다.