피보나치 수는 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 로 나눈 나머지를 출력한다.