나탈리아와 체자리는 게임을 즐기며, 특히 자신들이 직접 만든 게임을 가장 좋아합니다. 그들은 각 $m$개의 동전으로 이루어진 동전 더미들을 일렬로 배치하기로 했습니다. 각 동전은 파란색이거나 빨간색입니다. 나탈리아는 자신의 차례에 파란색 동전을 하나 골라, 그 동전과 그 위에 쌓인 모든 동전을 게임에서 제거할 수 있습니다. 마찬가지로 체자리는 자신의 차례에 빨간색 동전을 하나 골라, 그 동전과 그 위에 쌓인 모든 동전을 게임에서 제거할 수 있습니다. 두 플레이어는 번갈아 가며 움직이며, 더 이상 유효한 움직임을 할 수 없는 사람(즉, 자신의 색깔 동전이 모두 제거된 사람)이 패배합니다.

이제 그들은 게임의 초기 상태, 즉 각각 $m$개의 동전으로 구성된 $d$개의 더미를 결정해야 합니다. 나탈리아와 체자리는 어느 한쪽이 불공정한 이득을 얻는 것을 원치 않으므로, 더미의 배치가 '공정'해야 한다는 데 동의했습니다. 더미의 배치가 공정하다는 것은, 나탈리아와 체자리가 최적으로 플레이할 때, 첫 번째 움직임을 하지 않는 플레이어가 승리한다는 것을 의미합니다. 즉, 나탈리아가 먼저 움직이면 체자리가 승리하고, 체자리가 먼저 움직이면 나탈리아가 승리합니다.

그들은 이미 $m$개의 동전으로 구성된 $k$개의 더미를 배치했습니다. 이제 이 더미들을 어떻게 완성할지 고민하고 있습니다. 그들은 게임에 $n$개 이상의 더미가 있는 것은 의미가 없다고 결론지었습니다. 여러분은 그들을 도와 $[k, n]$ 범위의 각 $d$에 대해, 이미 배치된 더미들로 시작하여 $d$개의 더미로 구성된 공정한 배치가 몇 가지나 존재하는지 구해야 합니다. 두 더미 배치는 어떤 $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'로 이루어진 문자열이 주어집니다. $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

참고

첫 번째 예제에서, 더미를 추가하지 않으면 단일 더미는 공정하지 않습니다. 하지만 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$ 조건이 성립합니다.

위에서 언급된 각 경우는 이전 경우에서 언급되지 않은 최소 하나의 그룹을 설명합니다.