Hôm nay cả lớp được học về phép chia hết cho ~5~, cô giáo giao cho các bạn một bài tập như sau:

Cho số nguyên ~x~ ~(1 \le x \le 10^{10^6})~ và số nguyên ~k~ ~(1\le k \le 20)~. Hãy đếm số dãy con của ~x~ có độ dài ~k~ sao cho dãy con đó là một số nguyên có nghĩa và chia hết cho ~5~? Biết rằng, một số gọi là có nghĩa khi không bắt đầu bằng số ~0~, trừ khi nó là số có một chữ số.

Một dãy con của ~x~ được định nghĩa là một dãy các phần tử được tạo ra bằng cách chọn một số phần tử từ dãy ban đầu (không nhất thiết phải liên tiếp) nhưng vẫn giữ nguyên thứ tự ban đầu. Ví dụ, ta có ~x = 123456~, một dãy con của ~x~ có thể là ~125~ hoặc ~15~.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~x~ ~(1 \le x \le 10^{10^6})~.
• Dòng thứ hai chứa số nguyên ~k~ ~(1 \le k \le 20)~.

Kết quả ra

• Một dòng duy nhất chứa số dãy con thỏa đề bài. (modulo ~10^9 + 7~)

Ràng buộc

• Có ~40\%~ số test ứng với ~1 \le x \le 10^{20}~.
• Còn lại ~60\%~ số test không có ràng buộc gì thêm.

Ví dụ

Dữ liệu vào

100456
2

Kết quả ra

4

Giải thích

Các dãy con chia hết cho ~5~ từ dãy ban đầu:

~[1, 2]: 10~

~[1, 3]: 10~

~[1, 5]: 15~

~[4, 5]: 45~