Let's define the cost of a simple undirected graph as the sum of the costs of its nodes. The cost of a node is defined as D^K, where D is its degree.

You are given N and K. You need to find the sum of the costs of all possible simple undirected graphs with N nodes. As this number may be very large, output the sum modulo 1005060097.

Definitions
Here are a few definitions from graph theory in case you're not familiar with them.

An undirected graph is an ordered pair (V, E) consisting of a set V of nodes, and a set E of edges which consists of unordered pairs of nodes from V.

The degree of a node is the number of edges incident to it.

A simple undirected graph is an undirected graph with no loops and multiple edges. A loop is an edge connecting a node to itself. Multiple edges are two or more edges connecting the same pair of nodes.

Input Format
The first line contains the number of test cases T.
Each of the next T lines contains two integers N and K separated by a space.

Output Format
For each test case, output one line containing the sum of the costs of all possible simple undirected graphs with N nodes, modulo 1005060097.

Constraints
1 ≤ T ≤ 2·10⁵
1 ≤ N ≤ 10⁹
1 ≤ K ≤ 2·10⁵
The sum of the K's in a single test file is at most 2·10⁵.

Sample input

5
1 1
2 3
3 2
6 5
20 20

Sample Output

0
2
36
67584000
956922563

Explanation
In the first case, there is only one simple graph with 1 node, and the cost of that graph is 0¹ = 0.

In the second case, there are two simple graphs with 2 nodes, one with a single edge and one with no edges.
The cost of the graph with a single edge is 1³+1³ = 2.
The cost of the graph with no edges is 0³+0³ = 0.
Thus, the total is 2+0 = 2.

In the third case, there are eight simple graphs with 3 nodes.
There is one graph with three edges, and its cost is 2²+2²+2² = 12.
There are three graphs with two edges, and the cost of each is 1²+1²+2² = 6.
There are three graphs with one edge, and the cost of each is 0²+1²+1² = 2.
There is one graph with no edges, and its cost is 0²+0²+0² = 0.
Thus, the total is 12·1 + 6·3 + 2·3 + 0·1 = 36.