|
E |
Help Hermione Input: Standard Input Output: Standard Output |
|
Arithmancy is one of the most favorite subjects of Hermione Granger,
the most intelligent witch of her generation. She was thinking about the last homework given by Professor Vector:
A peculiar magical creature can live in a rectangle drawn into a n*n
square grid if and only if the rectangle
is not a square and its sides are parallel to the major axes. Same
conditions hold for higher dimensions (yes, the peculiar creature can even be 2500-dimensional!!!),
i.e. if the sides parallel to the major axes are all equal, it cannot live inside the hyper box. For example, in a
3-dimensional grid, it can live inside a 2*2*3 or a 3*4*5 box, but it cannot
live inside a 5*5*5 cube!! In how many ways one can draw a k-dimensional hyper box inside a n*n*...*n(k times n) grid so that
the peculiar creature can live inside the hyper box? A way is different from
another way if at least one co-ordinate of one corner is different. For
example, in a 4*4 grid, {(0,0), (0,3), (2,3), (2,0)}, {(1,0), (1,3), (3,3),
(3,0)} and {(0,0), (0,3), (4,3), (4,0)} are 3 different ways but {(0,0), (0,3),
(2,3), (2,0)}, {(0,3), (2,3), (2,0), (0,0)} and {(2,3), (2,0), (0,0), (0,3)}
are not different.
Hermione is quite confident of solving it, but she has to go now to the
Room of Requirement with Harry and Ron for a secret meeting. Your task is to
write a program that solves the problem for Hermione.
Input
The first line contains a single integer T (T ≤ 5,000) which denotes the number of test cases. Each
of the following T lines contains two integers, n (1 ≤
n ≤ 109) and k
(2 ≤ k ≤
2500).
Output
For each test case, output a single integer in each line which is the
number of ways to draw k-dimensional
axis-parallel hyper boxes in an n*n*….*n
grid. As this number can be quite large, output the answer mod 1,000,000,007 (109 + 7).
Sample
Input
Output for Sample Input
|
2 3 2 2 2 |
22 4 |