| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P154PROH - ROUND 4H - Đặt dấu |
Tí đang học toán trên lớp tuy nhiên cậu cảm thấy vô cùng nhàm chán nên cậu lấy ra một mẩu giấu và viết ra n chữ số trên cùng một dòng. Sau đó cậu chèn vào dãy n số đó các dấu “+”. Có nhiều cách đặt tuy nhiên, đều tuân thủ một số quy tắc sau. Giữa 2 chữ số có không quá 1 dấu “+”. Các dấu “+” luôn nằm giữa 2 chữ số nào đó. Ví dụ: Cách đặt 1 + 2 + 34 là đúng, các cách đặt ++1 + 2 + 34, 1 + 2 + 3 + 4 + là sai.
Có k dấu “+” và cậu phải đặt hết tất cả chúng vào dãy n số và phải đúng quy tắc.
Với mỗi cách đặt dấu cộng, cậu lại có một biểu thức, và cậu lại có một giá trị của biểu thức đó. Giờ cậu cộng tổng tất cả giá trị các biểu thức lại. Tuy nhiên, giờ cậu mới phát hiện ra giá trị sẽ rất lớn và cũng có quá nhiều cách đặt dấu cộng, cậu không thể làm được. Tí cần sự giúp đỡ của các bạn, hãy giúp Tí nhé!
Input
Dòng đầu tiên gồm 2 số nguyên n, k (0 <= k < n <= 10^5).
Dòng tiếp theo chứa n chữ số mà Tí viết trên giấy
Output
Gồm một dòng duy nhất là tổng giá trị các biểu thức sau khi lấy dư cho 10^9 + 7.
Example
Test 1:
Input:
3 1
108
Output:
27
Test 2:
Input:
3 2
108
Output:
9
Giải thích test 1:
Có 2 cách đặt
Cách đặt thứ nhất: 1 + 08 = 9
Cách đặt thứ hai: 10 + 8 = 18
Vậy tổng các giá trị biểu thức là 27
| Được gửi lên bởi: | adm |
| Ngày: | 2015-03-25 |
| Thời gian chạy: | 1s |
| 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 |
