11236: Poker and Power Sum

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

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.



Input

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

Output

For each data set, a single line of output should appear. This line should take the form of "v"(ignore the quotation mark), andvis the answer that Sheath want.

Sample Input Copy

1
1 2

Sample Output Copy

12