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 DK, 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^{5}

1 ≤ N ≤ 10^{9}

1 ≤ K ≤ 2·10^{5}

The sum of the K's in a single test file is at most 2·10^{5}.

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^{1} = 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^{3}+1^{3} = 2.

The cost of the graph with no edges is 0^{3}+0^{3} = 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^{2}+2^{2} = 12.

There are three graphs with two edges, and the cost of each is 1^{2}+1^{2}+2^{2} = 6.

There are three graphs with one edge, and the cost of each is 0^{2}+1^{2}+1^{2} = 2.

There is one graph with no edges, and its cost is 0^{2}+0^{2}+0^{2} = 0.

Thus, the total is 12·1 + 6·3 + 2·3 + 0·1 = 36.

见题面

见题面