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

Điểm: 5,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

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 | \cdot 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 \leq | a | \leq 10^{5}$ ), chỉ gồm các chữ số.
Dòng thứ hai chứa số nguyên $k$ ( $1 \leq k \leq 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 \leq | a | \leq 10^{5}$
$1 \leq k \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
1256 1	4	$s = 1256$ . Bốn số chia hết cho $5$ có thể tạo ra là: $5$ , $15$ , $25$ , $125$ .
555 2	63	$s = 555555$ . Bất kỳ tập con khác rỗng nào của $6$ chữ số đều chia hết cho $5$ , cho $2^{6} - 1 = 63$ cách.
13990 2	528	$s = 1399013990$ . Hai chữ số $0$ ở vị trí (1-indexed) $5$ và $10$ là vị trí có thể kết thúc một số chia hết cho $5$ , đóng góp $2^{4} + 2^{9} = 528$ cách.

Bình luận

Không có bình luận tại thời điểm này.