Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.