יש מחרוזת ארוכה $S$ של M ו-O ושלם $K \geq 1$. ספרו פירוקים לתת-סדרות MOOOO....O, בכל אחת בדיוק $K$ אותיות O, מודולו $10^9+7$.
המחרוזת ארוכה ולכן אינה נתונה במפורש. במקום זאת נתונים $L$ ($1 \leq L \leq 10^{18}$) ומחרוזת $T$ באורך $N$ ($1 \leq N \leq 10^6$). $S$ מחברת $L$ עותקים של $T$.
קלט
השורה הראשונה מכילה $K$, $N$ ו-$L$.
השנייה מכילה $T$ באורך $N$, כל תו M או O.
מובטח שמספר הפירוקים של $S$ אינו אפס.
פלט
הדפיסו את מספר הפירוקים של $S$ מודולו $10^9+7$.
דוגמאות
קלט 1
2 6 1
MOOMOOפלט 1
1הערה
הפירוק היחיד ל-MOO יוצר אחד משלושת התווים הראשונים ואחר משלושת האחרונים.
קלט 2
2 6 1
MMOOOOפלט 2
6הערה
יש שישה פירוקים שונים לתת-סדרות (האותיות הגדולות יוצרות MOO אחד והקטנות אחר):
MmOOooMmOoOoMmOooOMmoOOoMmoOoOMmooOO
קלט 3
1 4 2
MMOOפלט 3
4קלט 4
1 4 100
MMOOפלט 4
976371285הערה
הקפידו לקחת את התשובה מודולו $10^9+7$.
תתי משימות
- בדיקות 5–7: $K=1$, $L = 1$
- בדיקות 8–10: $K=2$, $N\leq 1000$, $L = 1$
- בדיקות 11–13: $K=1$
- בדיקות 14–19: $L = 1$
- בדיקות 20–25: אין מגבלות נוספות.
קרדיט לבעיה: Dhruv Rohatgi