탈출한 거위들

문제 정보

문제

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개의 댓글이 있습니다.