원숭이 먹이 나누기

한 식품과학 연구소가 건강한 식단이 원숭이의 행동에 미치는 영향을 연구하고 있다. 매일 원숭이들을 $G$개의 그룹으로 나눈다. 각 그룹에는 한 마리 이상의 원숭이가 있으며, 각 그룹은 다음 규칙에 따라 하루에 한 번 과일과 채소를 배급받는다.

• 각 원숭이는 채소를 최대 한 개까지 받는다.
• 한 그룹 안의 모든 원숭이는 같은 개수의 과일을 받는다(그렇지 않으면 원숭이들이 난동을 부린다).
• 한 그룹에서는 오직 한 종류의 과일과 한 종류의 채소만 사용할 수 있다.
• 서로 다른 두 그룹은 같은 종류의 과일이나 채소를 공유하지 않는다.
• 한 그룹이 받는 채소의 개수는 그 그룹에 속한 원숭이 수보다 반드시 적다.
• 각 그룹은 과일과 채소를 합쳐 최대 $M$개까지만 받을 수 있다.

하루 예산으로는 정확히 $B$개의 품목(과일과 채소)을 구입하며, 예산은 전부 소진해야 한다. 즉 구입한 모든 품목은 원숭이들에게 먹여야 한다. 모든 품목의 가격은 같고, $B < 100 \times M$ 이다.

예를 들어 원숭이가 각각 $3$마리와 $4$마리인 $2$개의 그룹이 있고, 예산이 $B = 5$, 그룹당 상한이 $M = 5$일 때, 먹이를 주는 서로 다른 방법은 $6$가지이다.

원숭이들에게 먹이를 주는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오.

첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $C$가 주어진다($1 < C < 100$).

이어지는 $C$개의 줄에는 각각 세 정수 $B$, $G$, $M$이 주어진다. $B$는 그날의 예산, $G$는 그룹의 수, $M$은 한 그룹이 받을 수 있는 품목(과일과 채소의 합)의 최대 개수이다. 범위는 $1 < B < 10{,}000{,}000$, $1 \le G < 100{,}000$, $1 < M < 100{,}000$ 이다.

각 테스트 케이스마다 원숭이들에게 먹이를 주는 서로 다른 방법의 수를 소수 $1{,}000{,}000{,}007$로 나눈 나머지로 한 줄에 하나씩 출력한다.