병아리의 변신은 무죄

학교 공부를 마치고 집으로 가던 다진이는 길가에서 병아리를 파는 아저씨를 발견했다. 병아리를 몹시 사고 싶었던 다진이는 병아리의 상태를 확인하지도 않고 한 마리를 사서 집으로 향했다. 다음 날, 다진이는 병아리를 보러 방에 갔는데 병아리 옆에 알이 하나 놓여 있었다. 분명 병아리만 산 다진이는 이상하다고 생각했지만 지각할 것 같아서 곧바로 학교로 갔다.

그날도 술을 마시고 바로 잔 다진이는 다음 날 일어나서 병아리가 2마리가 된 것을 보았다. 병아리들 옆에는 또 알이 하나 놓여 있었다. 병아리가 알을 낳는다는 말을 들어 본 적도 없었던 다진이는 그날부터 병아리를 관찰하기로 했다.

병아리는 매일 혼자서 알을 낳는다. 병아리가 낳은 알들은 K일 후에 다시 병아리로 태어난다. 병아리들은 죽지 않으며 병아리의 모습을 계속 유지한다.

병아리들을 관찰하던 다진이는 문득 N일 후에는 병아리가 몇 마리가 될지 궁금해졌다.

위 그림은 K = 0일 때의 상태를 나타낸다. K = 0이므로 병아리가 알을 낳자마자 알은 병아리로 부화한다. 그림에서 사각형은 병아리를 나타낸다. 다진이를 도와 N일 후의 병아리 수를 알아내자.

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

둘째 줄부터 T개의 줄에 테스트케이스가 한 줄에 하나씩 주어진다. 각 테스트케이스에는 정수 K와 N이 주어진다. (0 ≤ K ≤ 10, 1 ≤ N ≤ 100,000,000)

각 테스트케이스마다 N일 후의 병아리 수를 100,000,007로 나눈 나머지를 출력한다.

위 그림은 K = 2일 때의 상태를 나타낸다. K = 2이므로 병아리가 알을 낳은 후 2일이 지나면 병아리로 부화한다. 위 그림에서 원은 알을 나타낸다.