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.

Source: hackerrank | Difficulty: MEDIUM
Tags: Combinatorics


Solutions:
def inv(a, b):
	return pow(a, b - 2, b)

def lagrange(v, k, x, mod):
	if x <= k:
		return v[x]
	(inn, den) = (1, 1)
	for i in range(1, k + 1):
		inn = inn * (x - i) % mod
		den = den * (mod - i) % mod
	inn = inn * inv(den, mod) % mod
	ret = 0
	for i in range(k + 1):
		ret = (ret + v[i] * inn) % mod
		md1 = mod - (x - i) * (k - i) % mod
		md2 = (i + 1) * (x - i - 1) % mod
		if i != k:
			inn = inn * md1 % mod * inv(md2, mod) % mod
	return ret
from random import randint

def ilog2(n):
	return 0 if n <= 0 else n.bit_length() - 1

def pack(pack, shamt):
	size = len(pack)
	while size > 1:
		npack = []
		for i in range(0, size - 1, 2):
			npack += [pack[i] | pack[i + 1] << shamt]
		if size & 1:
			npack += [pack[-1]]
		(pack, size, shamt) = (npack, size + 1 >> 1, shamt << 1)
	return pack[0]

def unpack(M, size, shamt):
	(s, sizes) = (size, [])
	while s > 1:
		sizes += [s]
		s = s + 1 >> 1
	ret = [M]
	for size in sizes[::-1]:
		(mask, nret) = ((1 << shamt) - 1, [])
		for c in ret:
			nret += [c & mask, c >> shamt]
		(ret, shamt) = (nret[:size], shamt >> 1)
	return ret

def poly_mul_mod(f, g, mod):
	size = min(len(f), len(g))
	shift = ((mod - 1) ** 2 * size).bit_length()
	rsize = len(f) + len(g) - 1
	h = unpack(pack(f, shift) * pack(g, shift), rsize, shift * (1 << ilog2(rsize - 1)))
	return [int(x % mod) for x in h]

def ans(n, k, mod):
	mul = n * pow(2, (n - 1) * (n - 2) // 2, mod)
	n -= 1
	fact = [1] * (k + 10)
	for i in range(2, k + 10):
		fact[i] = i * fact[i - 1] % mod
	f = []
	g = []
	for i in range(0, k + 5):
		_inv = inv(fact[i], mod)
		f.append(_inv)
		g.append(pow(i, k, mod) * _inv % mod)
	h = poly_mul_mod(f, g, mod)
	del h[k + 1:]
	pw = pow(2, k, mod)
	for i in range(0, k + 1):
		h[i] = h[i] * fact[i] % mod
		_inv = inv(pow(2, i, mod), mod)
		h[i] = h[i] * pw * _inv % mod
	return mul * pow(2, n, mod) * inv(pw, mod) * lagrange(h, k, n, mod) % mod
for t in range(int(input())):
	(n, k) = map(int, input().split())
	print(ans(n, k, 1005060097))