Số kỳ diệu chia hết cho 5

Cho một xâu $a$ chỉ gồm các chữ số và một số nguyên dương $k$. Đặt $s$ là xâu nhận được khi nối $k$ bản sao của $a$ lại với nhau (do đó $s$ có độ dài $|a|·k$).

Bạn được phép xoá đi một số (có thể không xoá) chữ số của $s$, nhưng không được xoá tất cả. Các chữ số còn lại, giữ nguyên thứ tự, tạo thành một số (có thể có chữ số $0$ ở đầu).

Hãy đếm số cách xoá sao cho số nhận được chia hết cho $5$. Hai cách được coi là khác nhau nếu tập các vị trí bị xoá khác nhau. In ra kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng thứ nhất chứa xâu $a$ ($1\le |a|\le {10}^5$), chỉ gồm các chữ số.
• Dòng thứ hai chứa số nguyên $k$ ($1\le k\le {10}^9$).

Dữ liệu ra

In ra một số nguyên duy nhất — số cách xoá hợp lệ modulo ${10}^9+7$.

Ràng buộc

• $1\le |a|\le {10}^5$
• $1\le k\le {10}^9$

Ví dụ