• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

خشایار شاه -پادشاه اسپادانا- به تازگی رشته‌ای رمزی به طول \(n\) از کشور دوست و همسایه آپادانا دریافت کرده است.

ابتدا دو نوع رشته را تعریف می‌کنیم.

رشته‌ای را بلوک می‌نامیم اگر از یکی از حروف کوچک الفبا بعلاوه یک عدد طبیعی (بدون صفر در ابتدای آن) تشکیل شده باشد. برای مثال \(a123\) و \(f4\) بلوک هستند ولی \(1a\) و \(ab1\) و \(a02\) و \(a12b\) و \(12a\) بلوک نیستند. (دقت کنید که عدد طبیعی باید بعد از حرف بیاید)

رشته‌ای را مولد می‌نامیم اگر از یک یا چند بلوک تشکیل شده باشد. برای مثال \(a12b4d7\) رشته‌ای مولد است.

زیبایی یک رشته مولد را تعداد ارقام آن منهای تعداد حروف آن تعریف می‌کنیم. برای مثال زیبایی رشته \(a12b4d7\) برابر \(1\) است و زیبایی رشته \(a123b5\) برابر \(2\) است.

کشور آپادانا برای ارسال رشته رمزی به این شکل عمل می‌کند:‌

آن‌ها در ابتدا رشته‌ای مولد را در نظر می‌گیرند، فرض کنید این رشته از \(t\) بلوک تشکیل شده باشد. رشته \(res\) که در ابتدا تهی‌ست را در نظر بگیرید. آن‌ها \(t\) مرحله عملیات زیر را انجام می‌دهند:‌

در مرحله \(i\) ام حرف مربوط به بلوک \(i\) را در نظر می‌گیرند و آن‌ حرف را به انتهای \(res\) اضافه می‌کنند. سپس رشته \(res\) را به اندازه عدد مربوط به بلوک \(i\)ام تکرار می‌کنند و رشته \(res\) جدید ساخته می‌شود. در نهایت پس از انجام \(t\) مرحله، رشته \(res\) همان رشته رمزی‌ است.

برای مثال اگر رشته مولد برابر \(a1b2c4\) باشد، آنگاه پس از انجام \(t=3\) مرحله:
\[\phi \rightarrow a \rightarrow abab \rightarrow ababcababcababcababc\] رشته رمزی \(ababcababcababcababc\) به دست می‌آید.

خشایار شاه، رشته رمزی را به کیوان -مشاور اعظم- داده است و از او می‌خواهد تا بیابد که آیا رشته‌ای مولد وجود دارد که زیبایی آن \(k\) باشد و رشته رمزی را بسازد‌؟

کیوان پس از بررسی‌‌های فراوان فهمیده‌ است که طول رشته رمزی \(n\) است اما تنها \(m\) حرف اول این رشته به دست خشایارشاه رسیده‌است و \(n - m\) حرف باقی‌مانده مشخص نیستند. اکنون کیوان که کمی گیج شده است از شما می‌خواهد که تعداد رشته‌های مولدی را بیابید که

• زیبایی شان \(k\) باشد.
• رشته رمزی متناظر با آن‌ها طولش \(n\) باشد و \(m\) حرف اولش برابر با رشته‌ای باشد که به دست خشایارشاه رسیده است.

از آنجایی که این عدد ممکن است بزرگ باشد، باقی مانده آن را بر \(10^{9} + 7\) بیابید.

ورودی

در خط اول ورودی سه عدد \(n, m, k\) آماده است.

سپس اگر \(m > 0\) باشد رشته ای به طول \(m\) آمده است که \(m\) حرف اول رشته رمزی را مشخص می‌کند.

\[1 \le n \le 100\ 000 \] \[0 \le m \le n\] \[0 \le k \le 10^{9}\]

رشته ورودی تنها از حروف کوچک الفبای انگلیسی تشکیل شده است.

خروجی

در تنها خط خروجی جواب مساله را چاپ کنید.

زیر مسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۳۰	\(n \le 1\ 000\)
۲	۲۰	رشته ورودی تنها از حرف \(a\) تشکیل شده است.
۳	۵۰	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

2 2 0
aa

خروجی نمونه ۱

2

ورودی نمونه ۲

4 2 0
ab

خروجی نمونه ۲

677

ورودی نمونه ۳

2 0 0

خروجی نمونه ۳

702