Cho một số nguyên dương \(S\) có \(n\) chữ số. BRUH muốn xóa một vài chữ số của \(S\) (có thể không xóa nhưng không được phép xóa tất cả các chữ số) để thu được số "Ngũ Hành" - là số chia hết cho \(5\). Lưu ý: số sau khi xóa có thể chứa các chữ số \(0\) ở đầu (leading zeros).

BRUH muốn đếm số cách xóa để thu được số Ngũ Hành, hai cách xóa được gọi là khác nhau nếu một chữ số bị xóa trong cách này nhưng không bị xóa trong cách kia. Kết quả có thể rất lớn nên chỉ cần tính và in ra phần dư của nó khi chia cho \(10^9+7\).

Input

• Dòng đầu tiên chứa một xâu \(a\) thể hiện một số nguyên dương (\(1\leq |a|\leq10^5\), với \(|a|\) là kích thước của xâu \(a\));
• Dòng thứ hai chứa số nguyên dương \(k\) (\(1\leq k\leq10^9\)).

Số \(S\) được tạo thành bằng cách nối \(k\) xâu \(a\) lại với nhau. Nói cách khác: \(n=|a|\times k\).

Output

• In ra một số nguyên dương duy nhất là kết quả bài toán.

Ví dụ

Sample input 1

1253
1

Sample output 1

4

Sample input 2

3253935
2

Sample output 2

8772

Ràng buộc

• Subtask 1 (30%): \(k\leq10^6\);
• Subtask 2 (70%): \(k\leq10^9\).