C. Шидэт тав

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$n$ цифр агуулсан тоон цуваа $s$ өгөгджээ. Иахуб зарим цифрүүдийг ($0$ ширхэг байж болно, гэхдээ бүх цифрийг болохгүй) устгаж "шидэт тоо" буюу $5$-д хуваагддаг тоо үүсгэхийг хүсчээ. Үлдсэн тоо нь тэгээр эхэлж болно.

Иахуб ер нь өгөгдсөн $s$ зурвасаас хичнээн ширхэг "шидэт тоо" үүсгэж болохыг сонирхжээ. Хэрвээ устгагдсан цифрүүдийн байрлал ялгаатай байвал үүссэн тоонуудыг ялгаатайд тооцно.

Бас оролтонд $s$-г яаж өгж байгааг сайн анхаараарай.

Оролт

Эхний мөрөнд $a$ ($1 ≤ |a| ≤ 10^5$) тэмдэгт мөр өгөгдөнө.

Хоёр дахь мөрөнд $k$ ($1 ≤ k ≤ 10^9$) бүхэл тоо.

$s$-нь $a$-г $k$ удаа залгаж бичсэнтэй тэнцүү болно. Тэгэхлээр мөн $n = |a|·k$ гэсэн үг.

Гаралт

Хариу болох ганц тоог $1000000007$-д ($10^9+7$) хуваасан үлдэгдэл.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
1256
1
Гаралт
4
Оролт
13990
2
Гаралт
528
Оролт
555
2
Гаралт
63

Тэмдэглэл

In the first case, there are four possible ways to make a number that is divisible by 5: 5, 15, 25 and 125.

In the second case, remember to concatenate the copies of $a$. The actual plate is 1399013990.

In the third case, except deleting all digits, any choice will do. Therefore there are $2^{6} - 1 = 63$ possible ways to delete digits.

Сэтгэгдлүүдийг ачааллаж байна...