피보나치 수는 0과 1로 시작하며 다음 수는 앞의 두 피보나치 수의 합이 된다.
피보나치 수 몇개를 나열하면 다음과 같다

0, 1, 1, 2, 3, 5, 8, 13, ...

트라이보나치 수는 0, 0, 1 로 시작하며 다음 수는 앞의 세 트라이보나치 수의 합이 된다.

트라이보나치 수 몇개를 나열하면 다음과 같다.

0, 0, 1, 1, 2, 4, 7, 13, 24, ...

N-보나치 수는 N-1개의 0과 1개의 1로 시작하며 다음 수는 앞의 N개의 N-보나치 수의 합이 된다.

N-보나치 수열의 K번째 수를 1,000,000,007 로 나눈 나머지를 출력하는 프로그램을 작성하세요.

첫 줄에는 테스트 케이스 개수 T (1 <= T <= 50) 가 주어진다. 
각 테스트 케이스 마다 숫자 N(1 <= N <= 1,000) 과 K ( 1<= K <= 1,000,000) 가 각각 주어진다

각 테스트 케이스 별로 K번째 N-보나치 수를 1,000,000,007 로 나눈 나머지를 출력한다.