Tafy loves to go on picnic with his friends. On a day he goes to Chocoland with his 'm' friends. They all observes Chocoland very adventurous and makes plan to stay at night there.

They collected 'x' Chocofruits for their breakfast and goes to sleep at night. They do not know how much they have collected.

One of his friend wakes up and saw that one Chocofruit get disappeared because of Chocoland magic and he takes his part out of remaining Chocofruits and goes to sleep.

Another friend wakes up after sometime and saw the same Chocoland magic of disappearance and he takes his part out of remaining Chocofruits and goes to sleep, and this happens to all of his friends including Tafy. Early morning they wake up all together and saw the magic of disappearance and distribute the Chocofruit amongst themselves. After distributing equally no Chocofruit is left. All the distributions made are in positive integers. The Chocofruits are not cut down into pieces.

Input :

First line of input contains N, no. of test cases. The next line contains m no. of friend coming with Tafy.

Output:

For each test case you need to output x, how many no. of Chocofruits they have collected. Since answer may be very large you have to print x%100007.

Constraints:

1<=N<=5

2<=m<=15