16467번 - 병아리의 변신은 무죄

학교공부를 끝내고 집을 가던 다진이는 길가에서 병아리를 팔고 있는 아저씨를 발견했다. 병아리를 무척 사고 싶었던 다진이는 병아리의 상태를 확인하지도 않고 한 마리를 사서 집으로 향했다. 다음 날, 다진이는 병아리를 확인하려 방으로 갔는데 병아리 옆에는 웬 알이 하나 놓여져 있었다. 분명히 병아리만 산 다진이는 이상하다고 생각했지만 지각을 할 것 같아서 바로 학교로 갔다. 

그날도 술을 먹고 바로 잔 다진이는 다음 날 일어났는데, 병아리가 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일이 지나면 병아리로 부화한다. 위의 그림에서 원은 알을 나타낸다.