Natalia và Cezary thích chơi các trò chơi, và đặc biệt là những trò chơi do chính họ nghĩ ra. Họ quyết định xếp một dãy các chồng tiền xu, mỗi chồng có $m$ đồng, trong đó mỗi đồng xu có thể là màu xanh hoặc màu đỏ. Trong lượt của mình, Natalia có thể chọn bất kỳ đồng xu màu xanh nào và loại bỏ nó khỏi trò chơi cùng với tất cả các đồng xu nằm phía trên nó trong cùng một chồng. Tương tự, trong lượt của mình, Cezary có thể chọn bất kỳ đồng xu màu đỏ nào và loại bỏ nó cùng với tất cả các đồng xu nằm phía trên nó trong cùng một chồng. Các người chơi thực hiện lượt của mình luân phiên, và người thua cuộc là người không thể thực hiện một nước đi hợp lệ – tức là khi tất cả các đồng xu của họ đã bị loại bỏ khỏi trò chơi trước đó.

Khi đã biết luật chơi, họ cần xác định trạng thái ban đầu của trò chơi – một dãy gồm $d$ chồng tiền xu, mỗi chồng chứa đúng $m$ đồng. Cả Natalia và Cezary đều không muốn có lợi thế không công bằng, vì vậy họ đồng ý rằng dãy các chồng tiền xu phải là "công bằng". Một dãy các chồng tiền xu được gọi là công bằng nếu, giả sử Natalia và Cezary chơi tối ưu, người chiến thắng là người không thực hiện nước đi đầu tiên. Như vậy, nếu Natalia đi trước, thì với chiến thuật tối ưu, Cezary sẽ thắng, và ngược lại: nếu Cezary đi trước, thì Natalia sẽ thắng.

Họ đã xếp sẵn $k$ chồng tiền xu đầu tiên, mỗi chồng có $m$ đồng. Bây giờ họ tự hỏi làm thế nào để hoàn thành dãy các chồng tiền xu này. Họ đã đi đến kết luận rằng không có ý nghĩa gì khi có nhiều hơn $n$ chồng tiền xu trong trò chơi. Hãy giúp họ và với mỗi số $d$ trong khoảng $[k, n]$, hãy cho biết có bao nhiêu dãy công bằng gồm $d$ chồng tiền xu, mỗi chồng có $m$ đồng, bắt đầu bằng dãy các chồng tiền xu mà họ đã xếp sẵn. Hai dãy các chồng tiền xu được coi là khác nhau nếu tồn tại $i \in [1, d]$ và $j \in [1, m]$ sao cho đồng xu thứ $j$ trong chồng thứ $i$ là màu xanh trong dãy này và màu đỏ trong dãy kia.

Vì các kết quả này có thể rất lớn, bạn chỉ cần đưa ra phần dư của chúng khi chia cho $10^9 + 7$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào tiêu chuẩn chứa ba số nguyên $n, m$ và $k$ ($1 \le n \le 32$; $1 \le m \le 24$; $0 \le k \le n$), lần lượt biểu thị giới hạn số lượng chồng, số lượng đồng xu trong mỗi chồng và số lượng chồng đã được tạo sẵn.

$k$ dòng tiếp theo chứa mô tả các chồng đã được thiết lập; dòng thứ $i$ chứa một chuỗi ký tự 'N' và 'C' có độ dài đúng bằng $m$, biểu thị màu sắc của các đồng xu trong chồng thứ $i$, bắt đầu từ dưới lên. Nếu ký tự thứ $j$ của chuỗi này là 'N', thì đồng xu thứ $j$ từ dưới lên trong chồng thứ $i$ là màu xanh. Ngược lại, nếu ký tự là 'C', thì đồng xu đó là màu đỏ.

Dữ liệu ra

Dòng duy nhất của dữ liệu ra phải chứa một dãy gồm $n - k + 1$ số nguyên, trong đó số thứ $i$ phải là phần dư khi chia cho $10^9 + 7$ của số cách có thể mở rộng dãy thêm $i - 1$ chồng sao cho dãy cuối cùng là công bằng.

Ví dụ

Ví dụ 1

3 3 1
CCN

Kết quả 1

0 1 3

Ví dụ 2

2 1 0

Kết quả 2

1 0 2

Ví dụ 3

4 2 4
CN
NC
CC
NN

Kết quả 3

1

Ghi chú

Trong ví dụ đầu tiên, nếu chúng ta không thêm bất kỳ chồng nào, dãy một phần tử sẽ không công bằng. Tuy nhiên, chúng ta có thể thêm chồng NNC – dãy hai chồng như vậy sẽ là công bằng. Chúng ta có thể thêm hai chồng theo ba cách: [CCN, NNN], [NNN, CCN], [NCN, NCN].

Nhiệm vụ con

• Trong một số nhóm kiểm thử, điều kiện $k = n$ được thỏa mãn.
• Trong một số nhóm kiểm thử, các điều kiện $n \le 8$ và $m \le 8$ được thỏa mãn.
• Trong một số nhóm kiểm thử, các điều kiện $n \le 12$ và $m \le 13$ được thỏa mãn.
• Trong một số nhóm kiểm thử, điều kiện $n \le 16$ và $m \le 19$ được thỏa mãn.

Mỗi trường hợp được liệt kê ở trên mô tả ít nhất một nhóm không được đề cập trong các trường hợp trước đó.