+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- خشایار شاه -پادشاه اسپادانا- به تازگی **رشته‌ای رمزی** به طول $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 ```