돌아온 떡파이어

떡파이어가 늙지 않는 비결은 떡국이다.

떡파이어는 떡국을 먹은 그릇 수만큼 나이를 먹는다. 먹는 즉시 소화하므로 하루에 몇 그릇을 먹든 상관없다. 대신 하루라도 떡국을 먹지 않으면 그전까지 아무리 많이 먹었어도 그날 생을 마감한다.

디디는 어떤 떡파이어가 $M$째 날에 $N$세로 생을 마감했다는 사실만 알고 있다. 이 떡파이어가 나이를 먹어 온 과정이 몇 가지인지 세려고 하는데, 나이가 클수록 경우의 수가 걷잡을 수 없이 늘어나 손으로는 셀 수 없다.

떡파이어의 나이는 0세에서 시작한다. 나이를 먹는 과정은 첫째 날부터 $M$째 날까지 매일 먹은 그릇 수를 순서대로 늘어놓은 것이고, 하루라도 그릇 수가 다르면 다른 과정으로 센다. $M$째 날에는 떡국을 먹지 않았고, 그래서 그날 생을 마감했다.

$N$이 3이고 $M$이 3이면 과정은 두 가지다. 첫째 날 1그릇, 둘째 날 2그릇, 셋째 날 0그릇을 먹은 과정과 첫째 날 2그릇, 둘째 날 1그릇, 셋째 날 0그릇을 먹은 과정이다.

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

이어지는 $T$개 줄에 각각 정수 $N$($0 \le N \le 10^9$)과 $M$($1 \le M \le 10^9$)이 공백으로 구분되어 주어진다.

각 테스트 케이스마다 나이를 먹는 과정의 가짓수를 100007로 나눈 나머지를 한 줄에 하나씩 출력한다. 100007은 흔히 쓰는 나눗수가 아니니 주의한다.