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

---

آی مجری که به فکر بچه‌ها است، یادش رفته است که به فکر بچه‌ها است! او به جای قصه‌ی شبانگاهی می‌خواهد یک بازی راه بیاندازد تا بچه‌ها به سر کار بروند(فردا متوجه این موضوع می‌شوید) و خودش راحت بخوابد. او یک رشته بزرگ به بچه‌ها می‌دهد که فقط از ارقام تشکیل شده است. سپس از آنها می‌خواهد که تعداد زیر رشته‌های این رشته را پیدا کنند که اگر این زیر رشته را به عنوان یک عدد در نظر بگیریم، این عدد بر عدد اول $p$ بخش پذیر است. اگر کسی جواب درست را بدهد، آی مجری به او به اندازه‌ی آن عدد شیرینی خواهد داد. متاسفانه از آنجایی که بچه‌ها جواب این سوال را نمی‌دانند، سعی می‌کنند که هی عدد بپرانند تا اینکه آی مجری بگوید که درست گفته‌اند و شیرینی‌ها را به آن‌ها بدهد؛ اما برای اینکه شیرینی بیشتری بگیرند تلاش می‌کنند که عددهای بزرگی را به عنوان جواب به آی مجری بگویند غافل از اینکه جواب عدد بزرگی نیست... آن‌ها هی عدد می‌پرانند و آی مجری مجبور است که به آن‌ها بگوید که جوابشان درست است یا خیر و اینگونه است که نمی‌تواند بخوابد و چون اعداد بچه‌ها از جواب خیلی دور است متاسفانه آی مجری به این زودی‌ها نمی‌تواند بخوابد. حالا آی مجری از ایده‌اش پشیمان شده است و می‌خواهد خود جواب را بگوید و به همه شیرینی بدهد و مثل همیشه برایشان قصه بخواند تا خوابشان ببرد و او هم بتواند بخوابد اما متاسفانه الان دیر وقت است و او جواب را یادش نمی‌آید. به او کمک کنید که جواب را پیدا کند.

ورودی

ورودی شامل دو خط است که در خط اول رشته‌ مورد نظر می‌آید و در خط دوم عدد اول $p$. $$ 2 \le p \le 10^9 $$ طول رشته حداکثر $10^6$ می‌باشد. رشته تنها از ارقام تشکیل شده است.

خروجی

در تنها سطر خروجی تعداد زیررشته‌هایی از رشته‌ی ورودی را خروجی دهید که عدد متناظر با آن زیر رشته‌ بر $p$ بخش پذیر است.

مثال

ورودی نمونه ۱

3146
3

خروجی نمونه ۱

2

ورودی نمونه ۲

1313
13

خروجی نمونه ۲

3