Cho xâu ~a~ có ~n~ chữ số. Minh muốn xóa một vài chữ 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 ý rằng, số sau khi xóa đó có thể chứa các chữ số 0 ở đầu. Bây giờ Minh muốn đếm số cách có thể thu được số ngũ hành này, số cách này chia lấy dư cho ~10^9 + 7~. Hai cách gọi là khác nhau nếu tập các vị trí xóa trong số đó là khác nhau.

Xâu ~s~ được tạo thành bằng cách nối ~k~ xâu ~a~ với nhau.

Yêu cầu: Đếm số cách xóa các chữ số để thu được số chia hết cho 5, kết quả lấy dư cho ~10^9 + 7~.

Input

• Dòng đầu tiên cho một xâu ~a~ (chiều dài của xâu này ~1 \le |a| \le 10^5~).
• Dòng thứ hai chứa một số nguyên ~k~ (~1 \le k \le 10^9~).

Output

• Đưa ra số nguyên duy nhất là số cách chia lấy dư cho ~10^9 + 7~.

Sample Input 1

1256
1

Sample Output 1

4