Nông dân John đã tạo ra \(N(1 \leq N \leq 10^5)\) bài toán. Sau đó, ông thuê \(M(1 \leq M \leq 20)\) người giải bài, mỗi người sẽ đánh giá các bài toán là "dễ" hoặc "khó".
Mục tiêu của John bây giờ là tạo ra một bộ bài toán được sắp xếp theo thứ tự độ khó tăng dần, bao gồm một số bài của \(N%\) bài toán trên được sắp xếp theo thứ tự nào đó. Không được tồn tại hai bài toán nào mà một số người giải bài cho rằng bài toán ở sau là dễ nhưng bài toán ở trước là khó.
Đếm số tập bài toán khác rỗng khác nhau thỏa mãn, \(modulo\) \(10^9+7\) .

Input

• Dòng đầu tiên gồm 2 số \(N\) và \(M\).
• \(M\) dòng tiếp theo, mỗi dòng chứa một xâu có độ dài \(N\). Ký tự thứ \(i\) của xâu này là E nếu người giải bài cho rằng bài toán \(i\) là dễ, hoặc H nếu ngược lại.

Output

Số lượng bộ bài toán có thể tạo ra, \(modulo\) \(10^9+7\).

Scoring

• Subtask \(1\): \(M=1\)
• Subtask \(2\): \(M \leq 16\)
• Subtask \(3\): Không có điều kiện gì thêm.

Example

3 1
EHE

9

10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

33