주사위 굴리기

Albert 는 $0$ 부터 $G$ 까지 정수가 적혀있는 게임 보드와 $D$ 개의 면을 가진 주사위를 갖고 있는데, 주사위의 각 면에는 $1$ 부터 $D$ 까지의 정수가 적혀있다. Albert는 게임 보드의 $0$번에서 시작하여 주사위를 굴린 후 주사위의 눈 만큼 한 번에 (우측으로) 이동하여 $G$ 칸에 도착하는 놀이를 즐겨한다. 구체적으로, $x$번 칸에서 주사위를 굴려 나온 눈이 $k$ 라면 $x+k$ 번 칸으로 이동하는데, 이 때 $x+k \gt G$ 인 경우 $G$ 번 칸에 도달하는 것으로 한다.

가령 아래 그림과 같이 $G = 5$ 인 게임 보드가 있고 $D = 2$ 인 양면 주사위를 생각해보자.

이 때 $0$ 번 칸에서 $5$ 번 칸에 도착하는 방법은 아래와 같이 총 8가지가 있다 (이 때, 주사위의 눈이 무엇인지는 고려하지 않고, 게임 말이 방문한 칸만 고려한다).

• 가장 첫 번째 방법은 0-1-2-3-4-5 번 칸을 순서대로 도달하는 경우인데, 주사위의 눈이 다섯 번 연속하여 1이 나왔을 수도 있고, 1이 네 번 나온 후 마지막에 2가 나왔지만 4번 칸에서 곧바로 (6번 칸이 존재하지 않으므로) 5번 칸에 도달했을 수도 있다.
• 가장 마지막 (가장 아랫줄) 방법은 0번칸, 2번칸에서 주사위가 연속하여 2가 나와 4번칸에 도달한 후, 세 번째 주사위 눈에 관계없이 5번 칸에 도달한 경우이다.

Albert는 $G, D$ 값만 알면 총 몇 가지 다른 방법으로 마지막 칸에 도달할 수 있는지 계산할 수 있다고 생각하여 당신에게 도움을 요청했다. 다만 이 값이 매우 커질 수 있으니 $10^9 + 7$ 로 나눈 나머지를 구해 Albert를 도와주자.

입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스는 한 줄에 두 개의 정수 $G, D$가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답인 마지막 칸에 도달하는 방법의 가짓수를 $10^9+7$로 나눈 나머지를 각 줄에 출력하라.

• $1 \le T \le 50$
• $1 \le G \le 30,000$
• $1 \le D \le 100$