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
输出格式
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.1
1 2
12