Bạn có một xâu dài \(S\) gồm các ký tự M và O, cùng một số nguyên \(K\geq 1\). Hãy đếm số cách phân tách \(S\) thành các dãy con sao cho mỗi dãy con có dạng MOOOO....O với đúng \(K\) ký tự O, lấy modulo \(10^9+7\).

Vì xâu rất dài nên bạn không được cung cấp nó một cách tường minh. Thay vào đó, bạn được cho một số nguyên \(L\) (\(1\leq L\leq 10^{18}\)) và một xâu \(T\) độ dài \(N\) (\(1\leq N\leq 10^6\)). Xâu \(S\) là phép nối của \(L\) bản sao của xâu \(T\).

Dữ liệu vào

Dòng đầu tiên chứa \(K\), \(N\) và \(L\).

Dòng thứ hai chứa xâu \(T\) độ dài \(N\). Mỗi ký tự là M hoặc O.

Đảm bảo số cách phân tách \(S\) khác không.

Dữ liệu ra

In ra số cách phân tách xâu \(S\), lấy modulo \(10^9+7\).

Ví dụ

2 6 1
MOOMOO

1

2 6 1
MMOOOO

6

1 4 2
MMOO

4

1 4 100
MMOO

976371285

Phân nhóm

• Dữ liệu 5–7: \(K=1\), \(L=1\).
• Dữ liệu 8–10: \(K=2\), \(N\leq 1000\), \(L=1\).
• Dữ liệu 11–13: \(K=1\).
• Dữ liệu 14–19: \(L=1\).
• Dữ liệu 20–25: Không có ràng buộc bổ sung.

Đề bài: Dhruv Rohatgi.

Nguồn

USACO 2025 US Open Contest, Gold — Moo Decomposition: https://usaco.org/index.php?page=viewproblem2&cpid=1521