| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 512 MB | 46 | 32 | 27 | 67.500% |
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가지가 있다 (이 때, 주사위의 눈이 무엇인지는 고려하지 않고, 게임 말이 방문한 칸만 고려한다).
Albert는 $G, D$ 값만 알면 총 몇 가지 다른 방법으로 마지막 칸에 도달할 수 있는지 계산할 수 있다고 생각하여 당신에게 도움을 요청했다. 다만 이 값이 매우 커질 수 있으니 $10^9 + 7$ 로 나눈 나머지를 구해 Albert를 도와주자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스는 한 줄에 두 개의 정수 $G, D$가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답인 마지막 칸에 도달하는 방법의 가짓수를 $10^9+7$로 나눈 나머지를 각 줄에 출력하라.
5 1 1 5 1 5 2 5 3 2 3
1 1 8 13 2
예제 1: 0번 칸에서 1번 칸에 도달하는 방법이 유일하다.
예제 2: 주사위의 눈이 1밖에 없으므로 0-1-2-3-4-5 순서로 도달하는 방법이 유일하다.
예제 3: 본문에서 다루었다.
예제 4: 추가 설명 없음.
예제 5: 0-1-2 혹은 0-2로 방문하는 두 가지 방법이 가능하다.