The Chick's Transformation Is Not Guilty

On his way home after finishing his schoolwork, Dajin spotted a man selling chicks on the street. Dajin, who wanted a chick badly, bought one without even checking its condition and headed home. The next day, Dajin went to his room to check on the chick and found an egg lying next to it. Dajin, who had certainly bought only a chick, thought it was strange, but he was about to be late, so he went straight to school.

That day too, Dajin drank and fell asleep right away. When he woke up the next day, he saw that there were 2 chicks. Next to the chicks, another egg was lying there. Dajin had never heard of a chick laying eggs, so from that day on he decided to observe the chick.

A chick lays an egg by itself every day. The eggs a chick lays hatch into chicks again after K days. The chicks do not die and keep their chick form.

While observing the chicks, Dajin suddenly became curious how many chicks there would be after N days.

The figure above shows the state when K = 0. Since K = 0, an egg hatches into a chick as soon as the chick lays it. In the figure, squares represent chicks. Help Dajin find the number of chicks after N days.

The first line gives the number of test cases T. (1 ≤ T ≤ 100)

From the second line, T lines follow, one test case per line. Each test case gives the integers K and N. (0 ≤ K ≤ 10, 1 ≤ N ≤ 100,000,000)

For each test case, print the number of chicks after N days modulo 100,000,007.

The figure above shows the state when K = 2. Since K = 2, an egg hatches into a chick 2 days after the chick lays it. In the figure above, circles represent eggs.