Bạn có chuỗi dài $S$ gồm M, O và số nguyên $K \geq 1$. Đếm các cách phân rã thành dãy con MOOOO....O, mỗi dãy có đúng $K$ chữ O, lấy modulo $10^9+7$.

Chuỗi quá dài nên không được cho tường minh. Thay vào đó cho $L$ ($1 \leq L \leq 10^{18}$) và chuỗi $T$ dài $N$ ($1 \leq N \leq 10^6$). $S$ ghép $L$ bản sao của $T$.

Dữ liệu vào

Dòng đầu chứa $K$, $N$, $L$.

Dòng hai chứa $T$ dài $N$, mỗi ký tự là M hoặc O.

Bảo đảm số cách phân rã $S$ khác không.

Dữ liệu ra

In số cách phân rã $S$ modulo $10^9+7$.

Ví dụ

Dữ liệu vào 1

2 6 1
MOOMOO

Dữ liệu ra 1

1

Ghi chú

Cách duy nhất phân rã thành MOO là ba ký tự đầu tạo một dãy, ba ký tự cuối tạo dãy kia.

Dữ liệu vào 2

2 6 1
MMOOOO

Dữ liệu ra 2

6

Ghi chú

Có sáu cách phân rã khác nhau thành dãy con (chữ hoa tạo một MOO, chữ thường tạo dãy kia):

• MmOOoo
• MmOoOo
• MmOooO
• MmoOOo
• MmoOoO
• MmooOO

Dữ liệu vào 3

1 4 2
MMOO

Dữ liệu ra 3

4

Dữ liệu vào 4

1 4 100
MMOO

Dữ liệu ra 4

976371285

Ghi chú

Nhớ lấy đáp án modulo $10^9+7$.

Nhiệm vụ con

• Kiểm thử 5–7: $K=1$, $L = 1$
• Kiểm thử 8–10: $K=2$, $N\leq 1000$, $L = 1$
• Kiểm thử 11–13: $K=1$
• Kiểm thử 14–19: $L = 1$
• Kiểm thử 20–25: Không có ràng buộc thêm.

Ghi công bài toán: Dhruv Rohatgi