| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P155SUME - ROUND 5E - Số 5 |
Cho 1 số S có n chữ số. Bạn có thể xóa 1 vài chữ số (có thể không xóa nhưng không được xóa hết) sao cho kết quả thu được là 1 số chia hết cho 5. Những số như vậy gọi là số kỳ diệu. Lưu ý rằng kết quả có thể là 1 số có chữ số 0 ở đầu.
Nhiệm vụ của bạn là đếm số cách xóa để tạo thành số kỳ diệu. Kết quả thu được lấy phần dư cho 1 000 000 007 (109 + 7).
Input
Dòng đầu tiên gồm 1 xâu a (1 ≤ |s| ≤ 105) chỉ bao gồm các chữ số. Dòng thứ 2 là 1 số k (1 ≤ k ≤ 109). Số S được tạo bởi k lần xâu a, tức là n = |a|·k.
Output
Kết quả của bài toán.
Example
Input:555
2
Output:63
Giải thích: Số S là 555555. Có tất cả 26 – 1 cách xóa.
| Được gửi lên bởi: | adm |
| Ngày: | 2015-07-31 |
| Thời gian chạy: | 2s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
