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×5cube!! 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 2 32 22 Sample Output 22 4