Phân Tách Moo

Xâu $S$ được tạo bằng cách nối $L$ bản sao của xâu $T$ (độ dài $N$). Mỗi ký tự của $T$ là 'M' hoặc 'O'.

Một dãy con Moo là một dãy vị trí tăng dần trong $S$ gồm đúng $K+1$ vị trí: vị trí đầu tiên chứa ký tự 'M', $K$ vị trí còn lại đều chứa ký tự 'O'. Nói cách khác, các ký tự tại các vị trí đó ghép lại tạo thành xâu dạng "MOO...O" với đúng $K$ chữ 'O'.

Đếm số cách phân tách $S$ thành các dãy con Moo, tức số cách chia toàn bộ $N·L$ vị trí của $S$ thành các nhóm rời nhau, mỗi nhóm là một dãy con Moo. Hai cách phân tách được coi là khác nhau nếu tồn tại hai vị trí cùng nhóm trong cách này nhưng khác nhóm trong cách kia. In kết quả modulo ${10}^9+7$.

Dữ liệu vào

• Dòng 1: Ba số nguyên $K$, $N$, $L$.
• Dòng 2: Xâu $T$ độ dài $N$ chỉ chứa 'M' và 'O'.

Dữ liệu ra

Một số nguyên duy nhất: số cách phân tách modulo ${10}^9+7$. Nếu không có cách nào, in ra $0$.

Ràng buộc

• $1\le K\le {10}^6$
• $1\le N\le {10}^6$
• $1\le L\le {10}^{18}$

Ví dụ