| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P155PROC - ROUND 5C - Mã nhị phân |
Để truyền tin qua một lỗ sâu cần chuyển thông tin về dạng nhị phân cơ bản. Nhóm Cooper nhận được một khối dữ liệu phải mất hàng năm để xử lý trong đó có rất nhiều dữ liệu là dữ liệu không mong muốn bị nhiễu được máy thăm dò thu lại, được biết các mã nhị phân cần xử lý là những dãy nhị phân độ dài n và có chứa ít nhất một đoạn k số 1 liền kề.
Hãy đếm giúp anh ấy số dãy nhị phân cần xử lý.
Input
Dòng đầu tiên chứa số bộ test T (T <= 1000000).
T dòng tiếp theo mỗi dòng chứa hai số nguyên n và k (1 ≤ k < n ≤ 1000).
Output
T dòng, dòng thứ i chứa một số nguyên là kết quả của test thứ i. Vì kết quả có thể khá lớn nên hãy chia dư cho 1000000007.
Example
Input:5
5 3
2 1
10 3
95 19
14 13 Output:8
3
520
149012315
3
| Được gửi lên bởi: | adm |
| Ngày: | 2015-03-30 |
| 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 |
