여정

어느 날 호머는 집에서 심심해져 스프링필드 땅을 탐험하는 여정을 떠나기로 했다. 스프링필드 땅은 무한한 격자다. 호머의 집은 칸 $(0, 0)$에 있고, 그의 여정은 $N$개의 걸음으로 이루어지며, 각 걸음은 오른쪽으로 한 칸 이동하거나 아래로 한 칸 이동하는 것 중 하나다.

이미 지루해진 호머는 여정마저 지루해지길 원하지 않았다. 그래서 같은 방향으로 $K$걸음 연속을 넘게 움직이지 않기로 했다. 즉, 여정이 흥미롭다는 것은 연속한 $K+1$개의 걸음마다 호머가 두 방향으로 모두 움직인 경우를 말한다.

그림 1: $N = 5$, $K = 2$인 예 (첫 번째 테스트 케이스)

$N$과 $K$가 주어질 때, 호머가 만들 수 있는 흥미로운 여정의 수를 세시오. 두 여정은 어떤 $i$에 대해 첫 번째 여정의 $i$번째 걸음이 두 번째 여정의 $i$번째 걸음과 다르면 서로 다른 것으로 본다. 수가 클 수 있으므로 $1\,000\,000\,007$로 나눈 나머지를 출력하시오.

프로그램은 하나 이상의 테스트 케이스에 대해 채점된다. 입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어지고 ($1 \le T \le 500$), 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 정수 두 개가 공백 하나로 구분되어 있는 한 줄로 주어진다. 첫 번째 정수는 호머의 여정에 있는 걸음 수 $N$이고, 두 번째 정수 $K$는 호머가 같은 방향으로 연속해서 움직일 수 있는 최대 걸음 수다. 여기서 $0 \le N \le 10^5$, $0 \le K \le 10^5$이다.

각 테스트 케이스마다 호머가 만들 수 있는 서로 다른 여정의 수를 $1\,000\,000\,007$로 나눈 나머지를 한 줄에 출력한다.