11236: Poker and Power Sum

TeStatic and Moat played poker at teaching building 9 yesterday for a whole night. As the result of it, TeStatic owed Moat 1024 yuan. TeStatic can't pay it back, so he asks Sheath for help.

Just in time, Sheath is puzzled by a problem about power sum, so he is willing to lending TeStatic 1024 yuan if TeStatic can solve his problem.

Sheath let ps(k,n) be the sum of the power of the first n positive integers. and the number of k -combinations of a set with n elements is recorded as by Sheath. He'd like to find the double of the sum of the product of and ps(2j−1,n) , when j pass through the first k positive integers.

For this value will be to large, TeStatic just need to tell Sheath the remainder when the value divided by the 9th power of 10 and 7.

I.e. Let ps(k,n)=1^k+2^k+...+n^k , Sheath want the following value.

In the first line of input file, there's a positive integer T indicating how much data sets will be included.

Each of the next T lines will contains two integers k and n .

We guarantee that:

1≤T≤10

1≤k,n≤1000000

1
1 2

12