시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 108 24 21 28.767%

문제

떡파이어의 불로장생의 비밀은 바로 떡국이다.

떡파이어는 떡국을 먹은 그릇의 개수만큼 나이를 먹는다. 그들은 매일 떡국을 먹는데, 떡국을 먹는대로 바로 소화가 가능하기 때문에 하루에 얼마든지 원하는 만큼 떡국을 먹을 수 있다. 그러나 전에 떡국을 얼마나 먹었든지, 그들은 기구하게도 떡국을 하루라도 먹지 않으면 생을 마감하게 된다.

어느 날, 디디는 어떤 떡파이어가 M째날에 N세로 생을 마감하기까지 어떤 생을 살아왔는지 알고 싶어서, 그의 나이를 먹는 과정의 경우의 수를 세려고 한다. 그렇지만, 떡파이어의 나이가 많을 수록 그 경우의 수는 무수히 많아지기 때문에 디디는 곤란해하고 있다.

그런 디디를 위해 M째날에 N세로 생을 마감한 떡파이어가 나이를 먹는 과정의 경우의 수를 세는 프로그램을 작성해야 한다.

떡파이어의 나이는 0세부터 시작된다.

N = 3, M = 3,일때를 예로 들면,

  • 첫째 날 1개 둘째 날 2개, 셋째 날 0개
  • 첫째 날 2개 둘째 날 1개, 셋째 날 0개

총 경우의 수는 2이다.

입력

첫째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 1000)가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 N(0 ≤ N ≤ 109)과 M(1 ≤ M ≤ 109)이 공백으로 구분되어 주어진다.

출력

각 테스트 케이스마다 한 줄에 하나씩 나이를 먹는 방법의 가짓 수를 100007로 나눈 나머지를 출력하시오. 100007은 일반적이지 않은 나눗수임에 유의하라.

예제 입력 1

1
3 3

예제 출력 1

2

출처

Contest > 네블컵 > 제 1회 네블컵 L번