탈출한 거위들

문제 정보

문제

KAIST 오리연못에는 각각 0,1,2, \cdots ,N-1로 이름이 부여된 N마리의 거위가 살고 있다. 어느 화창한 날, 몇몇 거위들이 단체로 반항을 일으키며 탈출 계획을 세웠고 총 K마리의 거위가 탈출에 성공하였다. 급해진 당신은 목격자를 찾다가, 유일한 목격자인 오리에게 다음과 같은 정보를 얻었다.

탈출한 거위들의 숫자의 합은 N으로 나누어 떨어진다.

당신의 할 일은 가능한 탈출한 거위들의 집합이 총 몇 가지인가를 구하는 것이다.

입력

입력은 T개의 테스트 케이스로 구성된다. 입력의 첫 줄에는 T가 주어진다.
각 테스트 케이스에 대해, 두 정수 N, K가 주어진다. (1 \le N \le 500, 1 \le K \le \min(N,100))

출력

각 테스트 케이스마다 한 줄에 가능한 총 경우수를 1,000,000,007 로 나눈 나머지를 출력한다.

예제 입력

3
7 4
1 1
58 4

예제 출력

5
1
7322

노트

2개의 댓글이 있습니다.