You are planning the next FIFA World Cup and you are counting the number of highways that need to be built to connect the cities with the venue. 

Your country has $n$ cities and all cities lie on a single straight road called “Highway Road”. If you want to go from City ${x}$ to City $y$ ( where $x\leq y$ ), you need to go through city $x,x+1,x+2,\cdots,y-1,y$. 

The requirements for the highways are as follows:

All games will be held in the $n^{th}$ city.
New bidirectional roads, called "Super Highways", need to be built such that it is possible to visit the $n^{th}$ city from any other city directly.  

You also have the cost to fulfil the second condition. The engineering team knows that if the length of a Super Highway is ${l}$, then it will cost $l^{k}$, where ${k}}$ is an integer constant.The length of Super Highway between city $\boldsymbol{x}$ and $y$ is $|x-y|$.  

For this problem, you need to find only a rough estimation of the cost, hence, find Total Cost Modulo $1000000009$. 

Input Format

First line will contain a single positive integer ${q}$ denoting the number of queries. Then for each case there will be two positive integers, $n$ and ${k}}$.

Constraints

$1\leq q\leq200$  
$1\leq n\leq10^{18}$  
$1\leq k\leq1000$

Output Format

For each case find the cost to build Super Highways such that it is possible to visit $n^{th}$ city from any other city directly. You have to print this value Modulo $1000000009$.

Sample Input 0
1
4 2

Sample Output 0
13

Explanation 0

There are four cities. We need to build Super Highways that connect city ${1}$ to city ${4}$ and city $2$ to city ${4}$. No need to connect city 3 with city ${4}$ since they are adjacent on “Highway Road”. So cost is $(4-1)^2+(4-2)^2=3^2+2^2=13$.

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Starter code:

Solutions:
import time
from fractions import Fraction as fr
from math import floor

def euclidean_alg(a, b):
	rm1 = a
	sm1 = 1
	tm1 = 0
	r = b
	s = 0
	t = 1
	while r != 0:
		q = rm1 // r
		temp_r = rm1
		temp_s = sm1
		temp_t = tm1
		rm1 = r
		sm1 = s
		tm1 = t
		r = temp_r - q * rm1
		s = temp_s - q * sm1
		t = temp_t - q * tm1
	return (rm1, sm1, tm1)

def modular_inverse(n, p):
	(r, s, t) = euclidean_alg(n, p)
	return s
modulus = 10 ** 9 + 9

def bernoulli_mod(n, modulus):
	res = []
	A = []
	for m in range(n + 1):
		A.append(modular_inverse(m + 1, modulus))
		for j in range(m, 0, -1):
			A[j - 1] = j * (A[j - 1] - A[j]) % modulus
		res.append(A[0])
	return res
bern = bernoulli_mod(1001, modulus)

def solve(n, k):
	if n <= 2:
		return 0
	ans = 0
	bin = 1
	for j in range(k + 1):
		ans = (ans + bin * bern[j] * pow(n - 1, k + 1 - j, modulus)) % modulus
		bin = bin * (k + 1 - j) * modular_inverse(j + 1, modulus) % modulus
	ans = (ans * modular_inverse(k + 1, modulus) - 1) % modulus
	return ans
q = int(input())
for i in range(q):
	(n, k) = [int(val) for val in input().split()]
	print(solve(n, k))


import sys
mod = 10 ** 9 + 9
B = [0 for _ in range(1001)]
inv = [i for i in range(10001)]
fac = [i for i in range(10001)]
fac[0] = 1
for i in range(1, 10001):
	inv[i] = pow(i, mod - 2, mod)
for i in range(1, 10001):
	fac[i] = fac[i - 1] * i
	fac[i] %= mod
invfac = fac[:]
for i in range(len(invfac)):
	invfac[i] = pow(invfac[i], mod - 2, mod)

def comb(n, k):
	return fac[n] * invfac[n - k] * invfac[k] % mod
B[0] = 1
B[1] = (mod - 1) * pow(2, mod - 2, mod) % mod
for m in range(2, 1001):
	for k in range(m):
		B[m] -= comb(m, k) * B[k] * inv[m - k + 1] % mod
		B[m] %= mod
B[1] = mod - B[1]

def f(n, p):
	res = 0
	for k in range(p + 1):
		res += comb(p, k) * B[p - k] * pow(n, k + 1, mod) * inv[k + 1] % mod
		res %= mod
	return res

def highwayConstruction(n, k):
	if n <= 2:
		return 0
	return (f(n - 1, k) + mod - 1) % mod
q = int(input().strip())
for a0 in range(q):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	result = highwayConstruction(n, k)
	print(result)


import sys
p = 10 ** 9 + 9
invs = [pow(i, p - 2, p) for i in range(1002)]

def highwayConstruction(n, k, b):
	n %= p
	if n == 1 or n == 0:
		return 0
	ninv = pow(n, p - 2, p)
	s = 0
	kchoosei = 1
	pown = n
	for i in range(k + 1):
		t = kchoosei * b[k - i] % p * pown % p * invs[i + 1] % p
		s = (s + t) % p
		kchoosei *= k - i
		kchoosei %= p
		kchoosei *= invs[i + 1]
		kchoosei %= p
		pown *= n
		pown %= p
	return (s - 1) % p

def computeBernoulli():
	b = [0] * 1001
	b[0] = 1
	for m in range(1, 1001):
		m1choosek = 1
		s = 0
		for k in range(m):
			s += m1choosek * b[k] % p
			s %= p
			m1choosek *= (m - k + 1) * invs[k + 1]
			m1choosek %= p
		b[m] = -s * invs[m + 1] % p
	return b
q = int(input().strip())
b = computeBernoulli()
for a0 in range(q):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	result = highwayConstruction(n, k, b)
	print(result)


def extended_gcd(aa, bb):
	(lastremainder, remainder) = (abs(aa), abs(bb))
	(x, lastx, y, lasty) = (0, 1, 1, 0)
	while remainder:
		(lastremainder, (quotient, remainder)) = (remainder, divmod(lastremainder, remainder))
		(x, lastx) = (lastx - quotient * x, x)
		(y, lasty) = (lasty - quotient * y, y)
	return (lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1))

def modinv(a, m):
	(g, x, y) = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m

def A000367_list_mod(n, mod):
	T = [0 for i in range(1, n + 2)]
	T[0] = 1
	T[1] = 1
	for k in range(2, n + 1):
		T[k] = (k - 1) * T[k - 1] % mod
	for k in range(2, n + 1):
		for j in range(k, n + 1):
			T[j] = ((j - k) * T[j - 1] + (j - k + 2) * T[j]) % mod
	a = 0
	b = 6
	s = 1
	for k in range(1, n + 1):
		T[k] = s * T[k] * k * modinv(b, mod) % mod
		h = b
		b = (20 * b - 64 * a) % mod
		a = h
		s = -s
	return T
mod = 1000000009
B2i = A000367_list_mod(500, mod)
B = [0 for _ in range(1001)]
B[1] = modinv(-2, mod)
for i in range(0, 1001, 2):
	B[i] = B2i[i >> 1]

def sum_pow_int(n, k):
	res = 0
	comb = 1
	for j in range(k + 1):
		Bj = B[j]
		k1j = k + 1 - j
		if Bj != 0:
			res = (res + comb * Bj * pow(n + 1, k1j, mod)) % mod
		comb = comb * k1j * modinv(j + 1, mod) % mod
	res = res * modinv(k + 1, mod) % mod
	return res

def highwayConstruction(n, k):
	if n < 3:
		return 0
	return (sum_pow_int(n - 1, k) - 1) % mod
q = int(input().strip())
for a0 in range(q):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	result = highwayConstruction(n, k)
	print(result)


MOD = 1000000009
f = [1, 1]
inf = [1, 1]
for i in range(5000):
	f.append((i + 2) * f[i + 1] % MOD)
	inf.append(pow(i + 2, MOD - 2, MOD) * inf[i + 1] % MOD)

def nCr(n, r):
	return f[n] * inf[r] * inf[n - r] % MOD
bern = [1, 500000005, 833333341, 0, 633333339, 0, 976190485, 0, 633333339, 0, 469696974, 0, 160805862, 0, 833333342, 0, 574509802, 0, 607769484, 0, 269696443, 0, 7252569, 0, 160719282, 0, 834758858, 0, 88793724, 0, 375425307, 0, 458194177, 0, 447972532, 0, 840005835, 0, 147911937, 0, 906304171, 0, 835100855, 0, 790434390, 0, 18465409, 0, 219852826, 0, 729430218, 0, 549724558, 0, 185958893, 0, 966180022, 0, 875441660, 0, 163991022, 0, 122478099, 0, 356692668, 0, 852972500, 0, 843757650, 0, 263617252, 0, 612272568, 0, 983136603, 0, 460777770, 0, 440931647, 0, 1931634, 0, 537844370, 0, 329269021, 0, 664160220, 0, 301809573, 0, 147947308, 0, 209437816, 0, 487053062, 0, 903512931, 0, 38883016, 0, 399980359, 0, 832893605, 0, 137659912, 0, 32046654, 0, 96201969, 0, 272382393, 0, 984809722, 0, 567516997, 0, 277826241, 0, 129450247, 0, 859219181, 0, 495505064, 0, 8707610, 0, 149991844, 0, 197841389, 0, 415837901, 0, 452556555, 0, 255969333, 0, 587269527, 0, 263414781, 0, 832704626, 0, 646359153, 0, 886506266, 0, 485734315, 0, 770784160, 0, 229289872, 0, 784336735, 0, 410524300, 0, 585080214, 0, 141553402, 0, 425223057, 0, 237545850, 0, 63589729, 0, 33858933, 0, 325120530, 0, 395472691, 0, 961112492, 0, 920184514, 0, 418233316, 0, 328311025, 0, 88615861, 0, 818164287, 0, 583547044, 0, 880260567, 0, 227383121, 0, 652754015, 0, 195906609, 0, 143074934, 0, 826044587, 0, 387905283, 0, 604711815, 0, 42021458, 0, 18853119, 0, 261939927, 0, 570870708, 0, 936427877, 0, 22903034, 0, 332187245, 0, 174614373, 0, 11038394, 0, 363254813, 0, 525874981, 0, 658368378, 0, 396296094, 0, 783547564, 0, 20855970, 0, 562367802, 0, 949243780, 0, 211426253, 0, 798316326, 0, 2189158, 0, 549188555, 0, 65168462, 0, 558688513, 0, 614620286, 0, 597722193, 0, 560494311, 0, 673146368, 0, 51251074, 0, 481381363, 0, 701221794, 0, 610905740, 0, 538953990, 0, 735130715, 0, 122194196, 0, 840631161, 0, 315715642, 0, 476095583, 0, 89037894, 0, 197626168, 0, 379851231, 0, 352939984, 0, 1603881, 0, 495686568, 0, 452061366, 0, 22791554, 0, 467084765, 0, 112929067, 0, 26339868, 0, 641824014, 0, 151097054, 0, 27572593, 0, 128712039, 0, 336837738, 0, 136194315, 0, 827051682, 0, 733043040, 0, 940867749, 0, 601253373, 0, 77767278, 0, 414299962, 0, 932037775, 0, 738226723, 0, 239077453, 0, 393853968, 0, 722937698, 0, 91409035, 0, 545345048, 0, 114641356, 0, 148877819, 0, 262317365, 0, 250818962, 0, 921863573, 0, 594138284, 0, 216245249, 0, 268198006, 0, 644235673, 0, 45020701, 0, 15197600, 0, 932257660, 0, 233031406, 0, 893606130, 0, 102728268, 0, 844873407, 0, 402162002, 0, 818789428, 0, 29315973, 0, 246877693, 0, 786369190, 0, 190539628, 0, 650370482, 0, 336782181, 0, 307008561, 0, 182715307, 0, 32544774, 0, 199166544, 0, 936317371, 0, 472944157, 0, 996413699, 0, 308540076, 0, 724760508, 0, 278710238, 0, 728549643, 0, 895187549, 0, 597018742, 0, 891332152, 0, 213314275, 0, 232858337, 0, 769598130, 0, 60714296, 0, 513821745, 0, 334412618, 0, 355998556, 0, 155515182, 0, 272958997, 0, 91080539, 0, 289948741, 0, 18208039, 0, 228396089, 0, 685375239, 0, 932013571, 0, 354972820, 0, 142772925, 0, 327077220, 0, 147126894, 0, 545255853, 0, 326621095, 0, 150434414, 0, 41482011, 0, 669751880, 0, 517959223, 0, 39900214, 0, 101166409, 0, 590690618, 0, 455010719, 0, 605684678, 0, 317918217, 0, 211140566, 0, 435382484, 0, 401548394, 0, 598150259, 0, 526705503, 0, 214208303, 0, 973980798, 0, 259608707, 0, 651883296, 0, 640931689, 0, 709670733, 0, 845424175, 0, 910642853, 0, 117887071, 0, 940539107, 0, 447181503, 0, 775851453, 0, 798595153, 0, 646557270, 0, 598371650, 0, 182121197, 0, 216655153, 0, 233674960, 0, 348110444, 0, 969342628, 0, 941227791, 0, 927291817, 0, 548282982, 0, 35494838, 0, 193345727, 0, 634083526, 0, 848413421, 0, 692263441, 0, 141039063, 0, 420990465, 0, 99968958, 0, 885427102, 0, 974652496, 0, 710104495, 0, 758887858, 0, 657847149, 0, 905536919, 0, 138925594, 0, 961365471, 0, 792067907, 0, 830174595, 0, 887505348, 0, 856653405, 0, 66520656, 0, 464436811, 0, 931952940, 0, 183318987, 0, 89044938, 0, 470198525, 0, 100406774, 0, 2440362, 0, 314128474, 0, 443702464, 0, 253825927, 0, 458301637, 0, 517281429, 0, 216517109, 0, 115148439, 0, 352788208, 0, 524532489, 0, 731457312, 0, 867734240, 0, 702581780, 0, 384432913, 0, 998018408, 0, 799667103, 0, 766683031, 0, 255467277, 0, 769679929, 0, 446799771, 0, 506785884, 0, 90367510, 0, 810460783, 0, 390906268, 0, 739257138, 0, 173415006, 0, 188140175, 0, 540061588, 0, 567270286, 0, 424512513, 0, 502150529, 0, 213408829, 0, 413161595, 0, 961560788, 0, 510494972, 0, 838316082, 0, 879558681, 0, 830705431, 0, 591747767, 0, 237101735, 0, 140378135, 0, 852001724, 0, 331668928, 0, 708252241, 0, 68662461, 0, 182555116, 0, 893538359, 0, 936149439, 0, 951194459, 0, 486306514, 0, 271650811, 0, 699214099, 0, 765695912, 0, 19806886, 0, 205867235, 0, 580303862, 0, 31389524, 0, 219423408, 0, 665425392, 0, 799852916, 0, 744435881, 0, 762868613, 0, 310465177, 0, 526023846, 0, 658432441, 0, 742149662, 0, 110910902, 0, 258750411, 0, 409162808, 0, 977047796, 0, 43894115, 0, 480488643, 0, 268465155, 0, 100559602, 0, 867519227, 0, 633379197, 0, 98138438, 0, 916305323, 0, 103527234, 0, 695952670, 0, 51702511, 0, 697247040, 0, 269625520, 0, 512484589, 0, 959771857, 0, 139799501, 0, 182818844, 0, 360880892, 0, 676601375, 0, 571409550, 0, 423527592, 0, 998937450, 0, 911882358, 0, 357372431, 0, 569826883, 0, 927762812, 0, 789489021, 0, 941796576, 0, 176041796, 0, 72554256, 0, 301167323, 0, 13654611, 0, 452813689, 0, 51503670, 0, 762831889, 0, 585781233, 0, 121672429, 0, 305331100, 0, 967289676, 0, 154103581, 0, 257678198, 0, 977205795, 0, 980551098, 0, 223350161, 0, 894968118, 0, 917907055, 0, 808738276, 0, 937225992, 0, 468349251, 0, 940092683, 0, 30717348, 0, 712135863, 0, 612214371, 0, 200486087, 0, 936406892, 0, 100110001, 0, 427337831, 0, 945651565, 0, 236598252, 0, 690549125, 0, 394737961, 0, 776706329, 0, 299478746, 0, 658529836, 0, 307757330, 0, 566747663, 0, 710125911, 0, 827130658, 0, 9983955, 0, 323916365, 0, 607915625, 0, 685905468, 0, 972001040, 0, 682676454, 0, 310811738, 0, 774922757, 0, 644321926, 0, 512199688, 0, 643906074, 0, 46604419, 0, 857891194, 0, 529476487, 0, 909815091, 0, 734569750, 0, 169167645, 0, 574820238, 0, 181574243, 0, 395929881, 0, 329346463, 0, 236503503, 0, 481065962, 0, 660068394, 0, 39488967, 0, 767760914, 0, 846703781, 0, 131607844, 0, 31944430, 0, 57414656, 0, 103890805, 0, 262746099, 0, 414410559, 0, 887714003, 0, 318008553, 0, 264525958, 0, 313716146, 0, 417633607, 0, 298841184, 0, 773043888, 0, 111856336, 0, 863238900, 0, 906822925, 0, 696923996, 0, 114496374, 0, 434214180, 0, 200788426, 0, 428710692, 0, 644886298, 0, 520452372, 0, 337637872, 0, 113445988, 0, 647989717, 0, 17926007, 0, 750915521, 0, 147574031, 0, 620849157, 0, 433572160, 0, 270718319, 0, 404134457, 0, 242824034, 0, 212675460, 0, 812599908, 0, 693194593, 0, 370922888, 0, 886952955, 0, 700862511, 0, 714683457, 0, 266781052, 0, 254450987, 0, 104223891, 0, 518390975]
t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	if n <= 2:
		print(0)
	else:
		n -= 1
		sum = 0
		for i in range(k + 1):
			sum += nCr(k, i) * bern[k - i] * (pow(n, i + 1, MOD) * pow(i + 1, MOD - 2, MOD)) % MOD
		print(int(sum - 1) % MOD)


from math import factorial

def extEuclideanAlg(a, b):
	if b == 0:
		return (1, 0, a)
	else:
		(x, y, gcd) = extEuclideanAlg(b, a % b)
		return (y, x - y * (a // b), gcd)

def modInvEuclid(a, m):
	(x, y, gcd) = extEuclideanAlg(a, m)
	if gcd == 1:
		return x % m
	else:
		return None
s = [[0 for i in range(0, 1005)] for j in range(0, 1005)]
mod = 1000000009

def preprocess():
	for k in range(1, 1005):
		for j in range(1, 1005):
			if j == 1:
				s[k][j] = 1
			elif j > k:
				s[k][j] = 0
			else:
				s[k][j] = j % mod * (s[k - 1][j] % mod) % mod + s[k - 1][j - 1] % mod
preprocess()
q = int(input())
for i in range(0, q):
	(n, k) = map(int, input().split())
	if n == 1:
		print(0)
	else:
		n -= 1
		fact = [1 for j in range(0, k + 1)]
		for j in range(1, k + 1):
			if j == 1:
				fact[j] = n * (n + 1) // 2
			else:
				fact[j] = fact[j - 1] * (n + 1 - j) * modInvEuclid(j + 1, mod) % mod
		ans = 0
		for j in range(1, k + 1):
			ans = (ans + s[k][j] % mod * (factorial(j) % mod) * (fact[j] % mod) % mod) % mod
		ans -= 1
		print(ans)


MOD = 1000000009
maxval = 2100
invmod = {0: None, 1: 1}
fact = {0: 1, 1: 1}
invfact = {0: 1, 1: 1}
for i in range(2, maxval):
	invmod[i] = (MOD - MOD // i * invmod[MOD % i] % MOD) % MOD
	fact[i] = i * fact[i - 1] % MOD
	invfact[i] = invmod[i] * invfact[i - 1] % MOD
B = [1, 500000004, 833333341, 0, 633333339, 0, 976190485, 0, 633333339, 0, 469696974, 0, 160805862, 0, 833333342, 0, 574509802, 0, 607769484, 0, 269696443, 0, 7252569, 0, 160719282, 0, 834758858, 0, 88793724, 0, 375425307, 0, 458194177, 0, 447972532, 0, 840005835, 0, 147911937, 0, 906304171, 0, 835100855, 0, 790434390, 0, 18465409, 0, 219852826, 0, 729430218, 0, 549724558, 0, 185958893, 0, 966180022, 0, 875441660, 0, 163991022, 0, 122478099, 0, 356692668, 0, 852972500, 0, 843757650, 0, 263617252, 0, 612272568, 0, 983136603, 0, 460777770, 0, 440931647, 0, 1931634, 0, 537844370, 0, 329269021, 0, 664160220, 0, 301809573, 0, 147947308, 0, 209437816, 0, 487053062, 0, 903512931, 0, 38883016, 0, 399980359, 0, 832893605, 0, 137659912, 0, 32046654, 0, 96201969, 0, 272382393, 0, 984809722, 0, 567516997, 0, 277826241, 0, 129450247, 0, 859219181, 0, 495505064, 0, 8707610, 0, 149991844, 0, 197841389, 0, 415837901, 0, 452556555, 0, 255969333, 0, 587269527, 0, 263414781, 0, 832704626, 0, 646359153, 0, 886506266, 0, 485734315, 0, 770784160, 0, 229289872, 0, 784336735, 0, 410524300, 0, 585080214, 0, 141553402, 0, 425223057, 0, 237545850, 0, 63589729, 0, 33858933, 0, 325120530, 0, 395472691, 0, 961112492, 0, 920184514, 0, 418233316, 0, 328311025, 0, 88615861, 0, 818164287, 0, 583547044, 0, 880260567, 0, 227383121, 0, 652754015, 0, 195906609, 0, 143074934, 0, 826044587, 0, 387905283, 0, 604711815, 0, 42021458, 0, 18853119, 0, 261939927, 0, 570870708, 0, 936427877, 0, 22903034, 0, 332187245, 0, 174614373, 0, 11038394, 0, 363254813, 0, 525874981, 0, 658368378, 0, 396296094, 0, 783547564, 0, 20855970, 0, 562367802, 0, 949243780, 0, 211426253, 0, 798316326, 0, 2189158, 0, 549188555, 0, 65168462, 0, 558688513, 0, 614620286, 0, 597722193, 0, 560494311, 0, 673146368, 0, 51251074, 0, 481381363, 0, 701221794, 0, 610905740, 0, 538953990, 0, 735130715, 0, 122194196, 0, 840631161, 0, 315715642, 0, 476095583, 0, 89037894, 0, 197626168, 0, 379851231, 0, 352939984, 0, 1603881, 0, 495686568, 0, 452061366, 0, 22791554, 0, 467084765, 0, 112929067, 0, 26339868, 0, 641824014, 0, 151097054, 0, 27572593, 0, 128712039, 0, 336837738, 0, 136194315, 0, 827051682, 0, 733043040, 0, 940867749, 0, 601253373, 0, 77767278, 0, 414299962, 0, 932037775, 0, 738226723, 0, 239077453, 0, 393853968, 0, 722937698, 0, 91409035, 0, 545345048, 0, 114641356, 0, 148877819, 0, 262317365, 0, 250818962, 0, 921863573, 0, 594138284, 0, 216245249, 0, 268198006, 0, 644235673, 0, 45020701, 0, 15197600, 0, 932257660, 0, 233031406, 0, 893606130, 0, 102728268, 0, 844873407, 0, 402162002, 0, 818789428, 0, 29315973, 0, 246877693, 0, 786369190, 0, 190539628, 0, 650370482, 0, 336782181, 0, 307008561, 0, 182715307, 0, 32544774, 0, 199166544, 0, 936317371, 0, 472944157, 0, 996413699, 0, 308540076, 0, 724760508, 0, 278710238, 0, 728549643, 0, 895187549, 0, 597018742, 0, 891332152, 0, 213314275, 0, 232858337, 0, 769598130, 0, 60714296, 0, 513821745, 0, 334412618, 0, 355998556, 0, 155515182, 0, 272958997, 0, 91080539, 0, 289948741, 0, 18208039, 0, 228396089, 0, 685375239, 0, 932013571, 0, 354972820, 0, 142772925, 0, 327077220, 0, 147126894, 0, 545255853, 0, 326621095, 0, 150434414, 0, 41482011, 0, 669751880, 0, 517959223, 0, 39900214, 0, 101166409, 0, 590690618, 0, 455010719, 0, 605684678, 0, 317918217, 0, 211140566, 0, 435382484, 0, 401548394, 0, 598150259, 0, 526705503, 0, 214208303, 0, 973980798, 0, 259608707, 0, 651883296, 0, 640931689, 0, 709670733, 0, 845424175, 0, 910642853, 0, 117887071, 0, 940539107, 0, 447181503, 0, 775851453, 0, 798595153, 0, 646557270, 0, 598371650, 0, 182121197, 0, 216655153, 0, 233674960, 0, 348110444, 0, 969342628, 0, 941227791, 0, 927291817, 0, 548282982, 0, 35494838, 0, 193345727, 0, 634083526, 0, 848413421, 0, 692263441, 0, 141039063, 0, 420990465, 0, 99968958, 0, 885427102, 0, 974652496, 0, 710104495, 0, 758887858, 0, 657847149, 0, 905536919, 0, 138925594, 0, 961365471, 0, 792067907, 0, 830174595, 0, 887505348, 0, 856653405, 0, 66520656, 0, 464436811, 0, 931952940, 0, 183318987, 0, 89044938, 0, 470198525, 0, 100406774, 0, 2440362, 0, 314128474, 0, 443702464, 0, 253825927, 0, 458301637, 0, 517281429, 0, 216517109, 0, 115148439, 0, 352788208, 0, 524532489, 0, 731457312, 0, 867734240, 0, 702581780, 0, 384432913, 0, 998018408, 0, 799667103, 0, 766683031, 0, 255467277, 0, 769679929, 0, 446799771, 0, 506785884, 0, 90367510, 0, 810460783, 0, 390906268, 0, 739257138, 0, 173415006, 0, 188140175, 0, 540061588, 0, 567270286, 0, 424512513, 0, 502150529, 0, 213408829, 0, 413161595, 0, 961560788, 0, 510494972, 0, 838316082, 0, 879558681, 0, 830705431, 0, 591747767, 0, 237101735, 0, 140378135, 0, 852001724, 0, 331668928, 0, 708252241, 0, 68662461, 0, 182555116, 0, 893538359, 0, 936149439, 0, 951194459, 0, 486306514, 0, 271650811, 0, 699214099, 0, 765695912, 0, 19806886, 0, 205867235, 0, 580303862, 0, 31389524, 0, 219423408, 0, 665425392, 0, 799852916, 0, 744435881, 0, 762868613, 0, 310465177, 0, 526023846, 0, 658432441, 0, 742149662, 0, 110910902, 0, 258750411, 0, 409162808, 0, 977047796, 0, 43894115, 0, 480488643, 0, 268465155, 0, 100559602, 0, 867519227, 0, 633379197, 0, 98138438, 0, 916305323, 0, 103527234, 0, 695952670, 0, 51702511, 0, 697247040, 0, 269625520, 0, 512484589, 0, 959771857, 0, 139799501, 0, 182818844, 0, 360880892, 0, 676601375, 0, 571409550, 0, 423527592, 0, 998937450, 0, 911882358, 0, 357372431, 0, 569826883, 0, 927762812, 0, 789489021, 0, 941796576, 0, 176041796, 0, 72554256, 0, 301167323, 0, 13654611, 0, 452813689, 0, 51503670, 0, 762831889, 0, 585781233, 0, 121672429, 0, 305331100, 0, 967289676, 0, 154103581, 0, 257678198, 0, 977205795, 0, 980551098, 0, 223350161, 0, 894968118, 0, 917907055, 0, 808738276, 0, 937225992, 0, 468349251, 0, 940092683, 0, 30717348, 0, 712135863, 0, 612214371, 0, 200486087, 0, 936406892, 0, 100110001, 0, 427337831, 0, 945651565, 0, 236598252, 0, 690549125, 0, 394737961, 0, 776706329, 0, 299478746, 0, 658529836, 0, 307757330, 0, 566747663, 0, 710125911, 0, 827130658, 0, 9983955, 0, 323916365, 0, 607915625, 0, 685905468, 0, 972001040, 0, 682676454, 0, 310811738, 0, 774922757, 0, 644321926, 0, 512199688, 0, 643906074, 0, 46604419, 0, 857891194, 0, 529476487, 0, 909815091, 0, 734569750, 0, 169167645, 0, 574820238, 0, 181574243, 0, 395929881, 0, 329346463, 0, 236503503, 0, 481065962, 0, 660068394, 0, 39488967, 0, 767760914, 0, 846703781, 0, 131607844, 0, 31944430, 0, 57414656, 0, 103890805, 0, 262746099, 0, 414410559, 0, 887714003, 0, 318008553, 0, 264525958, 0, 313716146, 0, 417633607, 0, 298841184, 0, 773043888, 0, 111856336, 0, 863238900, 0, 906822925, 0, 696923996, 0, 114496374, 0, 434214180, 0, 200788426, 0, 428710692, 0, 644886298, 0, 520452372, 0, 337637872, 0, 113445988, 0, 647989717, 0, 17926007, 0, 750915521, 0, 147574031, 0, 620849157, 0, 433572160, 0, 270718319, 0, 404134457, 0, 242824034, 0, 212675460, 0, 812599908, 0, 693194593, 0, 370922888, 0, 886952955, 0, 700862511, 0, 714683457, 0, 266781052, 0, 254450987, 0, 104223891, 0, 518390975, 0, 347144478, 0, 82841519, 0, 745926148, 0, 603831134, 0, 6428086, 0, 448129469, 0, 939040483, 0, 952221912, 0, 222533518, 0, 752979497, 0, 766363324, 0, 416624647, 0, 344930019, 0, 848056611, 0, 344690856, 0, 99963570, 0, 909972835, 0, 989979700, 0, 250407549, 0, 137957501, 0, 204296838, 0, 242702451, 0, 473503294, 0, 547166809, 0, 108281501, 0, 740956245, 0, 588942381, 0, 382317236, 0, 299630901, 0, 763838434, 0, 774761519, 0, 249342382, 0, 876897409, 0, 769040123, 0, 933750278, 0, 812649723, 0, 641530241, 0, 915557964, 0, 257975945, 0, 717483912, 0, 509258762, 0, 759013101, 0, 14599791, 0, 50782729, 0, 955845965, 0, 799485933, 0, 277300027, 0, 975169431, 0, 487840229, 0, 965174994, 0, 760090551, 0, 647371015, 0, 388511766, 0, 515187081, 0, 168567716, 0, 409443584, 0, 620082396, 0, 883592991, 0, 727941607, 0, 139773987, 0, 80117702, 0, 765308950, 0, 828607081, 0, 692783949, 0, 156168695, 0, 624401747, 0, 790430402, 0, 245155952, 0, 967683266, 0, 74431053, 0, 150821081, 0, 767529412, 0, 70822984, 0, 368986352, 0, 781580382, 0, 412674907, 0, 728861839, 0, 551138346, 0, 538959782, 0, 551357439, 0, 169320813, 0, 508077646, 0, 387064975, 0, 486160941, 0, 846746350, 0, 443003582, 0, 315981835, 0, 909805742, 0, 27158635, 0, 720227234, 0, 598308150, 0, 705918893, 0, 878746285, 0, 85973700, 0, 134656036, 0, 460845514, 0, 667357584, 0, 908325445, 0, 105026818, 0, 726393493, 0, 827096798, 0, 770434772, 0, 199985351, 0, 641092683, 0, 250796581, 0, 608175853, 0, 282079427, 0, 907873873, 0, 247801892, 0, 345883646, 0, 724571756, 0, 546115273, 0, 821730057, 0, 424625993, 0, 13874286, 0, 60543025, 0, 463636794, 0, 812657326, 0, 601235103, 0, 870817682, 0, 113094999, 0, 703110809, 0, 667265379, 0, 522679139, 0, 474804635, 0, 980489609, 0, 858643930, 0, 735676565, 0, 231128561, 0, 584407090, 0, 698407580, 0, 503270781, 0, 758677129, 0, 596159033, 0, 169106235, 0, 949658455, 0, 25557768, 0, 220460041, 0, 802230383, 0, 407010848, 0, 73636525, 0, 432010516, 0, 231676284, 0, 838234070, 0, 932313879, 0, 351541145, 0, 874805189, 0, 90859471, 0, 458595453, 0, 960058711, 0, 119946734, 0, 575421308, 0, 511468121, 0, 758181430, 0, 562791668, 0, 740931876, 0, 960026730, 0, 960369588, 0, 992622706, 0, 136489670, 0, 797364849, 0, 148205448, 0, 498369592, 0, 778502837, 0, 122120228, 0, 552366258, 0, 241679568, 0, 26437738, 0, 808637815, 0, 409354818, 0, 390652915, 0, 369784765, 0, 849382194, 0, 261852500, 0, 558779397, 0, 19692692, 0, 100288624, 0, 287465174, 0, 72736817, 0, 152567682, 0, 497584212, 0, 615921121, 0, 682622183, 0, 382673199, 0, 321327982, 0, 952706455, 0, 506448731, 0, 183441019, 0, 506910362, 0, 64430024, 0, 410958260, 0, 336004421, 0, 408836493, 0, 99404188, 0, 951323452, 0, 774362213, 0, 915892781, 0, 406821881, 0, 386715599, 0, 649277, 0, 353246063, 0, 848297984, 0, 267178498, 0, 929923729, 0, 246192208, 0, 605988049, 0, 220897218, 0, 140343695, 0, 850613114, 0, 541099320, 0, 537242763, 0, 157421493, 0, 994797518, 0, 834994100, 0, 880765181, 0, 90472428, 0, 943477181, 0, 803183307, 0, 714151663, 0, 538185036, 0, 814891724, 0, 906443287, 0, 706819470, 0, 910818962, 0, 813146979, 0, 97950016, 0, 546024895, 0, 859992851, 0, 952298574, 0, 639351253, 0, 884652782, 0, 663535785, 0, 523778989, 0, 602564204, 0, 694144439, 0, 340811322, 0, 860849761, 0, 375415561, 0, 896232264, 0, 215020957, 0, 524791681, 0, 678015866, 0, 440059511, 0, 166416875, 0, 62390257, 0, 659121709, 0, 689772909, 0, 190139869, 0, 36161434, 0, 807061274, 0, 559225447, 0, 264095718, 0, 515676255, 0, 324575812, 0, 556220402, 0, 567917360, 0, 698870782, 0, 334594700, 0, 659211738, 0, 363373899, 0, 14311348, 0, 316152474, 0, 485520491, 0, 274903918, 0, 630691708, 0, 693369075, 0, 215640956, 0, 604235430, 0, 625745011, 0, 254198456, 0, 509991487, 0, 819846154, 0, 3353162, 0, 716735455, 0, 698810730, 0, 252306638, 0, 145822981, 0, 989155416, 0, 5717845, 0, 904948080, 0, 595361012, 0, 596312175, 0, 9478954, 0, 171044563, 0, 667472732, 0, 983688016, 0, 418137826, 0, 676501637, 0, 920605052, 0, 695318059, 0, 655072677, 0, 355473665, 0, 128894023, 0, 1514153, 0, 313601442, 0, 536673739, 0, 255044909, 0, 105149808, 0, 198347235, 0, 68472718, 0, 304866861, 0, 954498904, 0, 474064771, 0, 917234870, 0, 887327691, 0, 755296731, 0, 674339251, 0, 357616476, 0, 967355283, 0, 597902401, 0, 392989714, 0, 431723940, 0, 344097571, 0, 636126322, 0, 691047969, 0, 873878691, 0, 528458981, 0, 40907378, 0, 144529582, 0, 142860052, 0, 709422126, 0, 962085148, 0, 216062125, 0, 169813698, 0, 717244822, 0, 820316255, 0, 700933857, 0, 191343947, 0, 260277583, 0, 852643590, 0, 773024191, 0, 246910186, 0, 822719372, 0, 511385618, 0, 800636996, 0, 603855091, 0, 687915052, 0, 220893358, 0, 496374922, 0, 923462982, 0, 591452247, 0, 659238047, 0, 436100712, 0, 447901712, 0, 113149942, 0, 10205454, 0, 980882163, 0, 371408383, 0, 354163421, 0, 724635411, 0, 875983922, 0, 38605122, 0, 102253241, 0, 950818004, 0, 670213522, 0, 758993416, 0, 169444985, 0, 448343508, 0, 812890062, 0, 113287823, 0, 662914972, 0, 908281057, 0, 653406018, 0, 950526759, 0, 749616367, 0, 737790318, 0, 626882471, 0, 472974381, 0, 385522572, 0, 205342646, 0, 578905379, 0, 767919780, 0, 763668070, 0, 503815959, 0, 215949571, 0, 81691642, 0, 587385073, 0, 871885472, 0, 398071650, 0, 635662971, 0, 152254819, 0, 511606022, 0, 886272991, 0, 205855923, 0, 526064443, 0, 531858643, 0, 210680881, 0, 969760461, 0, 786832318, 0, 758747256, 0, 701826387, 0, 75464316, 0, 506982003, 0, 655154675, 0, 378355179, 0, 700453513, 0, 138437908, 0, 300104612, 0, 418031032, 0, 22267236, 0, 180181542, 0, 438789023, 0, 486012227, 0, 761372918, 0, 935017928, 0, 182426554, 0, 73219615, 0, 879295783, 0, 189411840, 0, 233329993, 0, 493139341, 0, 450867456, 0, 80352000, 0, 164451304, 0, 311449116, 0, 425652942, 0, 331687851, 0, 949658868, 0, 500201997, 0, 244815787, 0, 166788117, 0, 512024904, 0, 185116845, 0, 518856595, 0, 610524238, 0, 631040933, 0, 155682210, 0, 599408297, 0, 590108144, 0, 559747481, 0, 513417715, 0, 355075106, 0, 747586118, 0, 277152225, 0, 474892009, 0, 664117830, 0, 478844603, 0, 28278909, 0, 777275490, 0, 737601156, 0, 748033277, 0, 651735775, 0, 876944790, 0, 898404163, 0, 376745204, 0, 71731576, 0, 601213198, 0, 980174699, 0, 766193423, 0, 957962713, 0, 865816841, 0, 682519038, 0, 877340652, 0, 890151384, 0, 814412475, 0, 317291638, 0, 623942570, 0, 290717894, 0, 236739306, 0, 296069729, 0, 475821251, 0, 454473464, 0, 892329916, 0, 601799576, 0, 183108789, 0, 363094097, 0, 635844848, 0, 289616105, 0, 650673727, 0, 447393112, 0, 561984108, 0, 614067585, 0, 787339200, 0, 906675447, 0, 553231922, 0, 979485574, 0, 524951286, 0, 724378712, 0, 695010543, 0, 833470528, 0, 755908422, 0, 365866342, 0, 505304386, 0, 435851415, 0, 57783631, 0, 345008998, 0, 132698609, 0, 134827623, 0, 69820125, 0, 193170320, 0, 845185344, 0, 924914885, 0, 338704753, 0, 242605883, 0, 108052672, 0, 434520897, 0, 849907189, 0, 435609718, 0, 997811300, 0, 139632647, 0, 957940767, 0, 646645087, 0, 310673262, 0, 190915170, 0, 534433782, 0, 710301399, 0, 699643613, 0, 692579080, 0, 584329278, 0, 79614732, 0, 392122963, 0, 930825697, 0, 770456609, 0, 318837446, 0, 352482679, 0, 180978934, 0, 25025193, 0, 612403850, 0, 991590366, 0, 590208896, 0, 834873466, 0, 239985020, 0, 74557317, 0, 611042014, 0, 435898295, 0, 490004328, 0, 90968801, 0, 131637376, 0, 214244695, 0, 442384028, 0, 962185867, 0, 189680631, 0, 57909127, 0, 58638395, 0, 544856567, 0, 880046914, 0, 184509750, 0, 949086556, 0, 217060433, 0, 65398656, 0, 629744519, 0, 96152065, 0, 461165322, 0, 859865504, 0, 423913005, 0, 103875321, 0, 751262348, 0, 900136822, 351734420]

def ncr(n, r):
	if r == 0 or r == n:
		return 1
	return fact[n] * invfact[r] * invfact[n - r] % MOD

def powsum(n, p):
	ssum = 0
	npow = n % MOD
	for i in range(1, p + 2):
		delta = -1 if i == p else 1
		val = delta * ncr(p + 1, i) * B[p + 1 - i] * npow
		ssum = (ssum + val) % MOD
		npow = npow * n % MOD
	return ssum * invmod[p + 1] % MOD

def solve():
	(n, p) = map(int, input().strip().split())
	if n == 1:
		print(0)
		return
	ans = powsum(n - 1, p) - 1
	print(ans % MOD)
q = int(input().strip())
for _ in range(q):
	solve()


import sys
MOD = 1000000009
Factorial = [1] * 1002
Factorial_inverse = [1] * 1002
for k in range(1, 1002):
	Factorial[k] = Factorial[k - 1] * k % MOD
	Factorial_inverse[k] = pow(Factorial[k], MOD - 2, MOD)

def choose(a, b):
	return Factorial[a] * Factorial_inverse[b] * Factorial_inverse[a - b] % MOD
B = [1] * 1001
for m in range(1, 1001):
	S = 0
	for k in range(m):
		S = (S + choose(m, k) * B[k] * pow(m - k + 1, MOD - 2, MOD)) % MOD
	B[m] = (1 - S) % MOD

def highwayConstruction(n, k):
	sol = 0
	for j in range(k + 1):
		sol = (sol + pow(-1, j) * choose(k + 1, j) * B[j] * pow(n, k + 1 - j, MOD)) % MOD
	sol = sol * pow(k + 1, MOD - 2, MOD) % MOD
	return sol
q = int(input().strip())
for _ in range(q):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	factor = n // MOD
	rem = n % MOD
	if n == 1:
		print(0)
	else:
		result = factor * highwayConstruction(MOD, k) % MOD
		result = (result + highwayConstruction(rem, k) - 1) % MOD
		print(result)


import sys
sys.setrecursionlimit(100000)
B = [1, 500000005, 833333341, 0, 633333339, 0, 976190485, 0, 633333339, 0, 469696974, 0, 160805862, 0, 833333342, 0, 574509802, 0, 607769484, 0, 269696443, 0, 7252569, 0, 160719282, 0, 834758858, 0, 88793724, 0, 375425307, 0, 458194177, 0, 447972532, 0, 840005835, 0, 147911937, 0, 906304171, 0, 835100855, 0, 790434390, 0, 18465409, 0, 219852826, 0, 729430218, 0, 549724558, 0, 185958893, 0, 966180022, 0, 875441660, 0, 163991022, 0, 122478099, 0, 356692668, 0, 852972500, 0, 843757650, 0, 263617252, 0, 612272568, 0, 983136603, 0, 460777770, 0, 440931647, 0, 1931634, 0, 537844370, 0, 329269021, 0, 664160220, 0, 301809573, 0, 147947308, 0, 209437816, 0, 487053062, 0, 903512931, 0, 38883016, 0, 399980359, 0, 832893605, 0, 137659912, 0, 32046654, 0, 96201969, 0, 272382393, 0, 984809722, 0, 567516997, 0, 277826241, 0, 129450247, 0, 859219181, 0, 495505064, 0, 8707610, 0, 149991844, 0, 197841389, 0, 415837901, 0, 452556555, 0, 255969333, 0, 587269527, 0, 263414781, 0, 832704626, 0, 646359153, 0, 886506266, 0, 485734315, 0, 770784160, 0, 229289872, 0, 784336735, 0, 410524300, 0, 585080214, 0, 141553402, 0, 425223057, 0, 237545850, 0, 63589729, 0, 33858933, 0, 325120530, 0, 395472691, 0, 961112492, 0, 920184514, 0, 418233316, 0, 328311025, 0, 88615861, 0, 818164287, 0, 583547044, 0, 880260567, 0, 227383121, 0, 652754015, 0, 195906609, 0, 143074934, 0, 826044587, 0, 387905283, 0, 604711815, 0, 42021458, 0, 18853119, 0, 261939927, 0, 570870708, 0, 936427877, 0, 22903034, 0, 332187245, 0, 174614373, 0, 11038394, 0, 363254813, 0, 525874981, 0, 658368378, 0, 396296094, 0, 783547564, 0, 20855970, 0, 562367802, 0, 949243780, 0, 211426253, 0, 798316326, 0, 2189158, 0, 549188555, 0, 65168462, 0, 558688513, 0, 614620286, 0, 597722193, 0, 560494311, 0, 673146368, 0, 51251074, 0, 481381363, 0, 701221794, 0, 610905740, 0, 538953990, 0, 735130715, 0, 122194196, 0, 840631161, 0, 315715642, 0, 476095583, 0, 89037894, 0, 197626168, 0, 379851231, 0, 352939984, 0, 1603881, 0, 495686568, 0, 452061366, 0, 22791554, 0, 467084765, 0, 112929067, 0, 26339868, 0, 641824014, 0, 151097054, 0, 27572593, 0, 128712039, 0, 336837738, 0, 136194315, 0, 827051682, 0, 733043040, 0, 940867749, 0, 601253373, 0, 77767278, 0, 414299962, 0, 932037775, 0, 738226723, 0, 239077453, 0, 393853968, 0, 722937698, 0, 91409035, 0, 545345048, 0, 114641356, 0, 148877819, 0, 262317365, 0, 250818962, 0, 921863573, 0, 594138284, 0, 216245249, 0, 268198006, 0, 644235673, 0, 45020701, 0, 15197600, 0, 932257660, 0, 233031406, 0, 893606130, 0, 102728268, 0, 844873407, 0, 402162002, 0, 818789428, 0, 29315973, 0, 246877693, 0, 786369190, 0, 190539628, 0, 650370482, 0, 336782181, 0, 307008561, 0, 182715307, 0, 32544774, 0, 199166544, 0, 936317371, 0, 472944157, 0, 996413699, 0, 308540076, 0, 724760508, 0, 278710238, 0, 728549643, 0, 895187549, 0, 597018742, 0, 891332152, 0, 213314275, 0, 232858337, 0, 769598130, 0, 60714296, 0, 513821745, 0, 334412618, 0, 355998556, 0, 155515182, 0, 272958997, 0, 91080539, 0, 289948741, 0, 18208039, 0, 228396089, 0, 685375239, 0, 932013571, 0, 354972820, 0, 142772925, 0, 327077220, 0, 147126894, 0, 545255853, 0, 326621095, 0, 150434414, 0, 41482011, 0, 669751880, 0, 517959223, 0, 39900214, 0, 101166409, 0, 590690618, 0, 455010719, 0, 605684678, 0, 317918217, 0, 211140566, 0, 435382484, 0, 401548394, 0, 598150259, 0, 526705503, 0, 214208303, 0, 973980798, 0, 259608707, 0, 651883296, 0, 640931689, 0, 709670733, 0, 845424175, 0, 910642853, 0, 117887071, 0, 940539107, 0, 447181503, 0, 775851453, 0, 798595153, 0, 646557270, 0, 598371650, 0, 182121197, 0, 216655153, 0, 233674960, 0, 348110444, 0, 969342628, 0, 941227791, 0, 927291817, 0, 548282982, 0, 35494838, 0, 193345727, 0, 634083526, 0, 848413421, 0, 692263441, 0, 141039063, 0, 420990465, 0, 99968958, 0, 885427102, 0, 974652496, 0, 710104495, 0, 758887858, 0, 657847149, 0, 905536919, 0, 138925594, 0, 961365471, 0, 792067907, 0, 830174595, 0, 887505348, 0, 856653405, 0, 66520656, 0, 464436811, 0, 931952940, 0, 183318987, 0, 89044938, 0, 470198525, 0, 100406774, 0, 2440362, 0, 314128474, 0, 443702464, 0, 253825927, 0, 458301637, 0, 517281429, 0, 216517109, 0, 115148439, 0, 352788208, 0, 524532489, 0, 731457312, 0, 867734240, 0, 702581780, 0, 384432913, 0, 998018408, 0, 799667103, 0, 766683031, 0, 255467277, 0, 769679929, 0, 446799771, 0, 506785884, 0, 90367510, 0, 810460783, 0, 390906268, 0, 739257138, 0, 173415006, 0, 188140175, 0, 540061588, 0, 567270286, 0, 424512513, 0, 502150529, 0, 213408829, 0, 413161595, 0, 961560788, 0, 510494972, 0, 838316082, 0, 879558681, 0, 830705431, 0, 591747767, 0, 237101735, 0, 140378135, 0, 852001724, 0, 331668928, 0, 708252241, 0, 68662461, 0, 182555116, 0, 893538359, 0, 936149439, 0, 951194459, 0, 486306514, 0, 271650811, 0, 699214099, 0, 765695912, 0, 19806886, 0, 205867235, 0, 580303862, 0, 31389524, 0, 219423408, 0, 665425392, 0, 799852916, 0, 744435881, 0, 762868613, 0, 310465177, 0, 526023846, 0, 658432441, 0, 742149662, 0, 110910902, 0, 258750411, 0, 409162808, 0, 977047796, 0, 43894115, 0, 480488643, 0, 268465155, 0, 100559602, 0, 867519227, 0, 633379197, 0, 98138438, 0, 916305323, 0, 103527234, 0, 695952670, 0, 51702511, 0, 697247040, 0, 269625520, 0, 512484589, 0, 959771857, 0, 139799501, 0, 182818844, 0, 360880892, 0, 676601375, 0, 571409550, 0, 423527592, 0, 998937450, 0, 911882358, 0, 357372431, 0, 569826883, 0, 927762812, 0, 789489021, 0, 941796576, 0, 176041796, 0, 72554256, 0, 301167323, 0, 13654611, 0, 452813689, 0, 51503670, 0, 762831889, 0, 585781233, 0, 121672429, 0, 305331100, 0, 967289676, 0, 154103581, 0, 257678198, 0, 977205795, 0, 980551098, 0, 223350161, 0, 894968118, 0, 917907055, 0, 808738276, 0, 937225992, 0, 468349251, 0, 940092683, 0, 30717348, 0, 712135863, 0, 612214371, 0, 200486087, 0, 936406892, 0, 100110001, 0, 427337831, 0, 945651565, 0, 236598252, 0, 690549125, 0, 394737961, 0, 776706329, 0, 299478746, 0, 658529836, 0, 307757330, 0, 566747663, 0, 710125911, 0, 827130658, 0, 9983955, 0, 323916365, 0, 607915625, 0, 685905468, 0, 972001040, 0, 682676454, 0, 310811738, 0, 774922757, 0, 644321926, 0, 512199688, 0, 643906074, 0, 46604419, 0, 857891194, 0, 529476487, 0, 909815091, 0, 734569750, 0, 169167645, 0, 574820238, 0, 181574243, 0, 395929881, 0, 329346463, 0, 236503503, 0, 481065962, 0, 660068394, 0, 39488967, 0, 767760914, 0, 846703781, 0, 131607844, 0, 31944430, 0, 57414656, 0, 103890805, 0, 262746099, 0, 414410559, 0, 887714003, 0, 318008553, 0, 264525958, 0, 313716146, 0, 417633607, 0, 298841184, 0, 773043888, 0, 111856336, 0, 863238900, 0, 906822925, 0, 696923996, 0, 114496374, 0, 434214180, 0, 200788426, 0, 428710692, 0, 644886298, 0, 520452372, 0, 337637872, 0, 113445988, 0, 647989717, 0, 17926007, 0, 750915521, 0, 147574031, 0, 620849157, 0, 433572160, 0, 270718319, 0, 404134457, 0, 242824034, 0, 212675460, 0, 812599908, 0, 693194593, 0, 370922888, 0, 886952955, 0, 700862511, 0, 714683457, 0, 266781052, 0, 254450987, 0, 104223891]
M = 1000000009

def nkd(i, j):
	return M - 1 if i == j else 1
mmidict = {}

def mmi(a):
	if a in mmidict:
		return mmidict[a]
	t = 0
	newt = 1
	r = M
	newr = a
	while newr != 0:
		quotient = r // newr
		(t, newt) = (newt, t - quotient * newt)
		(r, newr) = (newr, r - quotient * newr)
	if r > 1:
		return 0
	if t < 0:
		t = t + M
	mmidict[a] = t
	return t
factdict = {}
factdict[0] = 1

def modfact(n):
	if n in factdict:
		return factdict[n]
	x = n * modfact(n - 1) % M
	factdict[n] = x
	return x

def modcomb(x, y):
	return modfact(x) * mmi(modfact(y)) % M * mmi(modfact(x - y)) % M

def bme(x, y):
	ans = 1
	mask = 1
	cur = x
	while mask <= y:
		if mask & y:
			ans *= cur
			ans %= M
		cur *= cur
		cur %= M
		mask <<= 1
	return ans

def highwayConstruction(n, k):
	if n <= 2:
		return 0
	sm = 0
	n = (n - 1) % M
	nx = bme(n, k + 1)
	for i in range(k + 1):
		mlt = 1
		mlt = mlt * modcomb(k + 1, i) % M
		mlt = mlt * B[i] % M
		mlt = mlt * nx % M
		nx = nx * mmi(n) % M
		sm = (sm + mlt) % M
	sm = sm * mmi(k + 1) % M
	sm = (sm - 1) % M
	return sm
q = int(input().strip())
for a0 in range(q):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	result = highwayConstruction(n, k)
	print(result)


import sys

def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L.append(0)
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total

def Bernoulli_number_list_mod(n, modulus, B=[], neg_one=-1, inverse_list=[]):
	if neg_one == -1:
		neg_one = pow_mod(m - 1, m - 2, m)
	m = len(B)
	while m <= n:
		s = 0
		if m % 2 and m > 1:
			B.append(0)
		else:
			choose = 1
			for i in range(0, m):
				s += choose * B[i] % modulus
				choose *= m + 1 - i
				choose //= i + 1
			s *= neg_one * inverse_list[m + 1]
			s %= modulus
			B.append(s)
		m += 1
	return B

def faulhaber(N, K, m, Bernoulli_number=[], inverses=[], neg_one=-1):
	if neg_one == -1:
		neg_one = pow_mod(m - 1, m - 2, m)
	if not inverses:
		inverse_list = [0 for i in range(0, 1004)]
		for i in range(0, 1004):
			inverse_list[i] = pow_mod(i, m - 2, m)
	else:
		inverse_list = inverses
	s = 0
	choose = 1
	neg_one = pow_mod(m - 1, m - 2, m)
	for j in range(0, K + 1):
		if j == 1:
			s += neg_one * choose * Bernoulli_number[j] * pow_mod(N, K + 1 - j, m) % m
		else:
			s += choose * Bernoulli_number[j] * pow_mod(N, K + 1 - j, m) % m
		s %= m
		choose *= K + 1 - j
		choose //= j + 1
	s *= pow_mod(K + 1, m - 2, m)
	s %= m
	return (s, Bernoulli_number)

def highwayConstruction(n, k, Bernoulli_list=[1], inverses=[], neg_one=-1):
	modulus = pow(10, 9) + 9
	if n == 1 or n == 2:
		return 0
	else:
		(fh, Bernoulli_list) = faulhaber(n - 1, k, modulus, Bernoulli_list, inverses, neg_one)
		fh -= 1
		if fh < 0:
			fh += modulus
	return fh
q = int(input().strip())
modulus = pow(10, 9) + 9
inverse_list = [0 for i in range(0, 1004)]
for i in range(0, 1004):
	inverse_list[i] = pow_mod(i, modulus - 2, modulus)
neg_one = pow_mod(modulus - 1, modulus - 2, modulus)
Bernoulli_number = Bernoulli_number_list_mod(1001, modulus, [1], neg_one, inverse_list)
for a0 in range(q):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	result = highwayConstruction(n, k, Bernoulli_number, inverse_list)
	print(result)


import sys
from fractions import Fraction
from functools import reduce
from operator import mul
from math import factorial
modulo = 1000000009

def knuth(n, k):
	res = 1
	for _ in range(k):
		res *= n
		n -= 1
	return res

def prepare_stirling(max_k):
	res = [[1], [0, 1]]
	for n in range(2, max_k):
		row = [0]
		for k in range(1, n + 1):
			first = k * res[n - 1][k] if k < n else 0
			temp_res = first + res[n - 1][k - 1]
			row.append(temp_res % modulo)
		res.append(row)
	return res

def highwayConstruction(n, k, stirling_table):
	if n == 1:
		return 0
	n = n % modulo - 1
	res = 0
	cur_knuth = knuth(n + 1, 2)
	for j in range(1, k + 1):
		temp = stirling_table[k][j] * cur_knuth // (j + 1)
		cur_knuth *= n - j
		res += temp
	return res % modulo - 1
max_k = 1
q = int(input().strip())
problem_def = []
for a0 in range(q):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	problem_def.append((n, k))
	max_k = max(max_k, k)
table = prepare_stirling(max_k + 1)
for (n, k) in problem_def:
	result = highwayConstruction(n, k, table)
	print(result)


b = [1, 500000004, 833333341, 0, 633333339, 0, 976190485, 0, 633333339, 0, 469696974, 0, 160805862, 0, 833333342, 0, 574509802, 0, 607769484, 0, 269696443, 0, 7252569, 0, 160719282, 0, 834758858, 0, 88793724, 0, 375425307, 0, 458194177, 0, 447972532, 0, 840005835, 0, 147911937, 0, 906304171, 0, 835100855, 0, 790434390, 0, 18465409, 0, 219852826, 0, 729430218, 0, 549724558, 0, 185958893, 0, 966180022, 0, 875441660, 0, 163991022, 0, 122478099, 0, 356692668, 0, 852972500, 0, 843757650, 0, 263617252, 0, 612272568, 0, 983136603, 0, 460777770, 0, 440931647, 0, 1931634, 0, 537844370, 0, 329269021, 0, 664160220, 0, 301809573, 0, 147947308, 0, 209437816, 0, 487053062, 0, 903512931, 0, 38883016, 0, 399980359, 0, 832893605, 0, 137659912, 0, 32046654, 0, 96201969, 0, 272382393, 0, 984809722, 0, 567516997, 0, 277826241, 0, 129450247, 0, 859219181, 0, 495505064, 0, 8707610, 0, 149991844, 0, 197841389, 0, 415837901, 0, 452556555, 0, 255969333, 0, 587269527, 0, 263414781, 0, 832704626, 0, 646359153, 0, 886506266, 0, 485734315, 0, 770784160, 0, 229289872, 0, 784336735, 0, 410524300, 0, 585080214, 0, 141553402, 0, 425223057, 0, 237545850, 0, 63589729, 0, 33858933, 0, 325120530, 0, 395472691, 0, 961112492, 0, 920184514, 0, 418233316, 0, 328311025, 0, 88615861, 0, 818164287, 0, 583547044, 0, 880260567, 0, 227383121, 0, 652754015, 0, 195906609, 0, 143074934, 0, 826044587, 0, 387905283, 0, 604711815, 0, 42021458, 0, 18853119, 0, 261939927, 0, 570870708, 0, 936427877, 0, 22903034, 0, 332187245, 0, 174614373, 0, 11038394, 0, 363254813, 0, 525874981, 0, 658368378, 0, 396296094, 0, 783547564, 0, 20855970, 0, 562367802, 0, 949243780, 0, 211426253, 0, 798316326, 0, 2189158, 0, 549188555, 0, 65168462, 0, 558688513, 0, 614620286, 0, 597722193, 0, 560494311, 0, 673146368, 0, 51251074, 0, 481381363, 0, 701221794, 0, 610905740, 0, 538953990, 0, 735130715, 0, 122194196, 0, 840631161, 0, 315715642, 0, 476095583, 0, 89037894, 0, 197626168, 0, 379851231, 0, 352939984, 0, 1603881, 0, 495686568, 0, 452061366, 0, 22791554, 0, 467084765, 0, 112929067, 0, 26339868, 0, 641824014, 0, 151097054, 0, 27572593, 0, 128712039, 0, 336837738, 0, 136194315, 0, 827051682, 0, 733043040, 0, 940867749, 0, 601253373, 0, 77767278, 0, 414299962, 0, 932037775, 0, 738226723, 0, 239077453, 0, 393853968, 0, 722937698, 0, 91409035, 0, 545345048, 0, 114641356, 0, 148877819, 0, 262317365, 0, 250818962, 0, 921863573, 0, 594138284, 0, 216245249, 0, 268198006, 0, 644235673, 0, 45020701, 0, 15197600, 0, 932257660, 0, 233031406, 0, 893606130, 0, 102728268, 0, 844873407, 0, 402162002, 0, 818789428, 0, 29315973, 0, 246877693, 0, 786369190, 0, 190539628, 0, 650370482, 0, 336782181, 0, 307008561, 0, 182715307, 0, 32544774, 0, 199166544, 0, 936317371, 0, 472944157, 0, 996413699, 0, 308540076, 0, 724760508, 0, 278710238, 0, 728549643, 0, 895187549, 0, 597018742, 0, 891332152, 0, 213314275, 0, 232858337, 0, 769598130, 0, 60714296, 0, 513821745, 0, 334412618, 0, 355998556, 0, 155515182, 0, 272958997, 0, 91080539, 0, 289948741, 0, 18208039, 0, 228396089, 0, 685375239, 0, 932013571, 0, 354972820, 0, 142772925, 0, 327077220, 0, 147126894, 0, 545255853, 0, 326621095, 0, 150434414, 0, 41482011, 0, 669751880, 0, 517959223, 0, 39900214, 0, 101166409, 0, 590690618, 0, 455010719, 0, 605684678, 0, 317918217, 0, 211140566, 0, 435382484, 0, 401548394, 0, 598150259, 0, 526705503, 0, 214208303, 0, 973980798, 0, 259608707, 0, 651883296, 0, 640931689, 0, 709670733, 0, 845424175, 0, 910642853, 0, 117887071, 0, 940539107, 0, 447181503, 0, 775851453, 0, 798595153, 0, 646557270, 0, 598371650, 0, 182121197, 0, 216655153, 0, 233674960, 0, 348110444, 0, 969342628, 0, 941227791, 0, 927291817, 0, 548282982, 0, 35494838, 0, 193345727, 0, 634083526, 0, 848413421, 0, 692263441, 0, 141039063, 0, 420990465, 0, 99968958, 0, 885427102, 0, 974652496, 0, 710104495, 0, 758887858, 0, 657847149, 0, 905536919, 0, 138925594, 0, 961365471, 0, 792067907, 0, 830174595, 0, 887505348, 0, 856653405, 0, 66520656, 0, 464436811, 0, 931952940, 0, 183318987, 0, 89044938, 0, 470198525, 0, 100406774, 0, 2440362, 0, 314128474, 0, 443702464, 0, 253825927, 0, 458301637, 0, 517281429, 0, 216517109, 0, 115148439, 0, 352788208, 0, 524532489, 0, 731457312, 0, 867734240, 0, 702581780, 0, 384432913, 0, 998018408, 0, 799667103, 0, 766683031, 0, 255467277, 0, 769679929, 0, 446799771, 0, 506785884, 0, 90367510, 0, 810460783, 0, 390906268, 0, 739257138, 0, 173415006, 0, 188140175, 0, 540061588, 0, 567270286, 0, 424512513, 0, 502150529, 0, 213408829, 0, 413161595, 0, 961560788, 0, 510494972, 0, 838316082, 0, 879558681, 0, 830705431, 0, 591747767, 0, 237101735, 0, 140378135, 0, 852001724, 0, 331668928, 0, 708252241, 0, 68662461, 0, 182555116, 0, 893538359, 0, 936149439, 0, 951194459, 0, 486306514, 0, 271650811, 0, 699214099, 0, 765695912, 0, 19806886, 0, 205867235, 0, 580303862, 0, 31389524, 0, 219423408, 0, 665425392, 0, 799852916, 0, 744435881, 0, 762868613, 0, 310465177, 0, 526023846, 0, 658432441, 0, 742149662, 0, 110910902, 0, 258750411, 0, 409162808, 0, 977047796, 0, 43894115, 0, 480488643, 0, 268465155, 0, 100559602, 0, 867519227, 0, 633379197, 0, 98138438, 0, 916305323, 0, 103527234, 0, 695952670, 0, 51702511, 0, 697247040, 0, 269625520, 0, 512484589, 0, 959771857, 0, 139799501, 0, 182818844, 0, 360880892, 0, 676601375, 0, 571409550, 0, 423527592, 0, 998937450, 0, 911882358, 0, 357372431, 0, 569826883, 0, 927762812, 0, 789489021, 0, 941796576, 0, 176041796, 0, 72554256, 0, 301167323, 0, 13654611, 0, 452813689, 0, 51503670, 0, 762831889, 0, 585781233, 0, 121672429, 0, 305331100, 0, 967289676, 0, 154103581, 0, 257678198, 0, 977205795, 0, 980551098, 0, 223350161, 0, 894968118, 0, 917907055, 0, 808738276, 0, 937225992, 0, 468349251, 0, 940092683, 0, 30717348, 0, 712135863, 0, 612214371, 0, 200486087, 0, 936406892, 0, 100110001, 0, 427337831, 0, 945651565, 0, 236598252, 0, 690549125, 0, 394737961, 0, 776706329, 0, 299478746, 0, 658529836, 0, 307757330, 0, 566747663, 0, 710125911, 0, 827130658, 0, 9983955, 0, 323916365, 0, 607915625, 0, 685905468, 0, 972001040, 0, 682676454, 0, 310811738, 0, 774922757, 0, 644321926, 0, 512199688, 0, 643906074, 0, 46604419, 0, 857891194, 0, 529476487, 0, 909815091, 0, 734569750, 0, 169167645, 0, 574820238, 0, 181574243, 0, 395929881, 0, 329346463, 0, 236503503, 0, 481065962, 0, 660068394, 0, 39488967, 0, 767760914, 0, 846703781, 0, 131607844, 0, 31944430, 0, 57414656, 0, 103890805, 0, 262746099, 0, 414410559, 0, 887714003, 0, 318008553, 0, 264525958, 0, 313716146, 0, 417633607, 0, 298841184, 0, 773043888, 0, 111856336, 0, 863238900, 0, 906822925, 0, 696923996, 0, 114496374, 0, 434214180, 0, 200788426, 0, 428710692, 0, 644886298, 0, 520452372, 0, 337637872, 0, 113445988, 0, 647989717, 0, 17926007, 0, 750915521, 0, 147574031, 0, 620849157, 0, 433572160, 0, 270718319, 0, 404134457, 0, 242824034, 0, 212675460, 0, 812599908, 0, 693194593, 0, 370922888, 0, 886952955, 0, 700862511, 0, 714683457, 0, 266781052, 0, 254450987, 0, 104223891, 0, 518390975]
n = 1005
p = 1000000009

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
fac = [0 for x in range(n)]
ifac = [0 for x in range(n)]
fac[0] = ifac[0] = 1
for i in range(1, n):
	fac[i] = i * fac[i - 1] % p
	ifac[i] = modinv(i, p) * ifac[i - 1] % p

def choose(a, b):
	return fac[a] * ifac[b] * ifac[a - b] % p
import sys

def highwayConstruction(n, k):
	n = n - 1
	inv = modinv(k + 1, p)
	s = 0
	for i in range(k + 1):
		s += pow(-1, i, p) * choose(k + 1, i) * b[i] * pow(n, k + 1 - i, p) % p
	sol = s * inv % p
	return sol - 1
q = int(input().strip())
for a0 in range(q):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	if n == 1:
		print(0)
	else:
		result = highwayConstruction(n, k)
		print(result)


import sys
m = 1000000009
from math import factorial
facts = [1, 1]
for i in range(2, 1003):
	facts.append(facts[-1] * i % m)
invfacts = []
for i in range(len(facts)):
	invfacts.append(pow(facts[i], m - 2, m))

def C(n, k):
	return facts[n] * invfacts[k] * invfacts[n - k] % m
B = [1, 500000005, 833333341, 0, 633333339, 0, 976190485, 0, 633333339, 0, 469696974, 0, 160805862, 0, 833333342, 0, 574509802, 0, 607769484, 0, 269696443, 0, 7252569, 0, 160719282, 0, 834758858, 0, 88793724, 0, 375425307, 0, 458194177, 0, 447972532, 0, 840005835, 0, 147911937, 0, 906304171, 0, 835100855, 0, 790434390, 0, 18465409, 0, 219852826, 0, 729430218, 0, 549724558, 0, 185958893, 0, 966180022, 0, 875441660, 0, 163991022, 0, 122478099, 0, 356692668, 0, 852972500, 0, 843757650, 0, 263617252, 0, 612272568, 0, 983136603, 0, 460777770, 0, 440931647, 0, 1931634, 0, 537844370, 0, 329269021, 0, 664160220, 0, 301809573, 0, 147947308, 0, 209437816, 0, 487053062, 0, 903512931, 0, 38883016, 0, 399980359, 0, 832893605, 0, 137659912, 0, 32046654, 0, 96201969, 0, 272382393, 0, 984809722, 0, 567516997, 0, 277826241, 0, 129450247, 0, 859219181, 0, 495505064, 0, 8707610, 0, 149991844, 0, 197841389, 0, 415837901, 0, 452556555, 0, 255969333, 0, 587269527, 0, 263414781, 0, 832704626, 0, 646359153, 0, 886506266, 0, 485734315, 0, 770784160, 0, 229289872, 0, 784336735, 0, 410524300, 0, 585080214, 0, 141553402, 0, 425223057, 0, 237545850, 0, 63589729, 0, 33858933, 0, 325120530, 0, 395472691, 0, 961112492, 0, 920184514, 0, 418233316, 0, 328311025, 0, 88615861, 0, 818164287, 0, 583547044, 0, 880260567, 0, 227383121, 0, 652754015, 0, 195906609, 0, 143074934, 0, 826044587, 0, 387905283, 0, 604711815, 0, 42021458, 0, 18853119, 0, 261939927, 0, 570870708, 0, 936427877, 0, 22903034, 0, 332187245, 0, 174614373, 0, 11038394, 0, 363254813, 0, 525874981, 0, 658368378, 0, 396296094, 0, 783547564, 0, 20855970, 0, 562367802, 0, 949243780, 0, 211426253, 0, 798316326, 0, 2189158, 0, 549188555, 0, 65168462, 0, 558688513, 0, 614620286, 0, 597722193, 0, 560494311, 0, 673146368, 0, 51251074, 0, 481381363, 0, 701221794, 0, 610905740, 0, 538953990, 0, 735130715, 0, 122194196, 0, 840631161, 0, 315715642, 0, 476095583, 0, 89037894, 0, 197626168, 0, 379851231, 0, 352939984, 0, 1603881, 0, 495686568, 0, 452061366, 0, 22791554, 0, 467084765, 0, 112929067, 0, 26339868, 0, 641824014, 0, 151097054, 0, 27572593, 0, 128712039, 0, 336837738, 0, 136194315, 0, 827051682, 0, 733043040, 0, 940867749, 0, 601253373, 0, 77767278, 0, 414299962, 0, 932037775, 0, 738226723, 0, 239077453, 0, 393853968, 0, 722937698, 0, 91409035, 0, 545345048, 0, 114641356, 0, 148877819, 0, 262317365, 0, 250818962, 0, 921863573, 0, 594138284, 0, 216245249, 0, 268198006, 0, 644235673, 0, 45020701, 0, 15197600, 0, 932257660, 0, 233031406, 0, 893606130, 0, 102728268, 0, 844873407, 0, 402162002, 0, 818789428, 0, 29315973, 0, 246877693, 0, 786369190, 0, 190539628, 0, 650370482, 0, 336782181, 0, 307008561, 0, 182715307, 0, 32544774, 0, 199166544, 0, 936317371, 0, 472944157, 0, 996413699, 0, 308540076, 0, 724760508, 0, 278710238, 0, 728549643, 0, 895187549, 0, 597018742, 0, 891332152, 0, 213314275, 0, 232858337, 0, 769598130, 0, 60714296, 0, 513821745, 0, 334412618, 0, 355998556, 0, 155515182, 0, 272958997, 0, 91080539, 0, 289948741, 0, 18208039, 0, 228396089, 0, 685375239, 0, 932013571, 0, 354972820, 0, 142772925, 0, 327077220, 0, 147126894, 0, 545255853, 0, 326621095, 0, 150434414, 0, 41482011, 0, 669751880, 0, 517959223, 0, 39900214, 0, 101166409, 0, 590690618, 0, 455010719, 0, 605684678, 0, 317918217, 0, 211140566, 0, 435382484, 0, 401548394, 0, 598150259, 0, 526705503, 0, 214208303, 0, 973980798, 0, 259608707, 0, 651883296, 0, 640931689, 0, 709670733, 0, 845424175, 0, 910642853, 0, 117887071, 0, 940539107, 0, 447181503, 0, 775851453, 0, 798595153, 0, 646557270, 0, 598371650, 0, 182121197, 0, 216655153, 0, 233674960, 0, 348110444, 0, 969342628, 0, 941227791, 0, 927291817, 0, 548282982, 0, 35494838, 0, 193345727, 0, 634083526, 0, 848413421, 0, 692263441, 0, 141039063, 0, 420990465, 0, 99968958, 0, 885427102, 0, 974652496, 0, 710104495, 0, 758887858, 0, 657847149, 0, 905536919, 0, 138925594, 0, 961365471, 0, 792067907, 0, 830174595, 0, 887505348, 0, 856653405, 0, 66520656, 0, 464436811, 0, 931952940, 0, 183318987, 0, 89044938, 0, 470198525, 0, 100406774, 0, 2440362, 0, 314128474, 0, 443702464, 0, 253825927, 0, 458301637, 0, 517281429, 0, 216517109, 0, 115148439, 0, 352788208, 0, 524532489, 0, 731457312, 0, 867734240, 0, 702581780, 0, 384432913, 0, 998018408, 0, 799667103, 0, 766683031, 0, 255467277, 0, 769679929, 0, 446799771, 0, 506785884, 0, 90367510, 0, 810460783, 0, 390906268, 0, 739257138, 0, 173415006, 0, 188140175, 0, 540061588, 0, 567270286, 0, 424512513, 0, 502150529, 0, 213408829, 0, 413161595, 0, 961560788, 0, 510494972, 0, 838316082, 0, 879558681, 0, 830705431, 0, 591747767, 0, 237101735, 0, 140378135, 0, 852001724, 0, 331668928, 0, 708252241, 0, 68662461, 0, 182555116, 0, 893538359, 0, 936149439, 0, 951194459, 0, 486306514, 0, 271650811, 0, 699214099, 0, 765695912, 0, 19806886, 0, 205867235, 0, 580303862, 0, 31389524, 0, 219423408, 0, 665425392, 0, 799852916, 0, 744435881, 0, 762868613, 0, 310465177, 0, 526023846, 0, 658432441, 0, 742149662, 0, 110910902, 0, 258750411, 0, 409162808, 0, 977047796, 0, 43894115, 0, 480488643, 0, 268465155, 0, 100559602, 0, 867519227, 0, 633379197, 0, 98138438, 0, 916305323, 0, 103527234, 0, 695952670, 0, 51702511, 0, 697247040, 0, 269625520, 0, 512484589, 0, 959771857, 0, 139799501, 0, 182818844, 0, 360880892, 0, 676601375, 0, 571409550, 0, 423527592, 0, 998937450, 0, 911882358, 0, 357372431, 0, 569826883, 0, 927762812, 0, 789489021, 0, 941796576, 0, 176041796, 0, 72554256, 0, 301167323, 0, 13654611, 0, 452813689, 0, 51503670, 0, 762831889, 0, 585781233, 0, 121672429, 0, 305331100, 0, 967289676, 0, 154103581, 0, 257678198, 0, 977205795, 0, 980551098, 0, 223350161, 0, 894968118, 0, 917907055, 0, 808738276, 0, 937225992, 0, 468349251, 0, 940092683, 0, 30717348, 0, 712135863, 0, 612214371, 0, 200486087, 0, 936406892, 0, 100110001, 0, 427337831, 0, 945651565, 0, 236598252, 0, 690549125, 0, 394737961, 0, 776706329, 0, 299478746, 0, 658529836, 0, 307757330, 0, 566747663, 0, 710125911, 0, 827130658, 0, 9983955, 0, 323916365, 0, 607915625, 0, 685905468, 0, 972001040, 0, 682676454, 0, 310811738, 0, 774922757, 0, 644321926, 0, 512199688, 0, 643906074, 0, 46604419, 0, 857891194, 0, 529476487, 0, 909815091, 0, 734569750, 0, 169167645, 0, 574820238, 0, 181574243, 0, 395929881, 0, 329346463, 0, 236503503, 0, 481065962, 0, 660068394, 0, 39488967, 0, 767760914, 0, 846703781, 0, 131607844, 0, 31944430, 0, 57414656, 0, 103890805, 0, 262746099, 0, 414410559, 0, 887714003, 0, 318008553, 0, 264525958, 0, 313716146, 0, 417633607, 0, 298841184, 0, 773043888, 0, 111856336, 0, 863238900, 0, 906822925, 0, 696923996, 0, 114496374, 0, 434214180, 0, 200788426, 0, 428710692, 0, 644886298, 0, 520452372, 0, 337637872, 0, 113445988, 0, 647989717, 0, 17926007, 0, 750915521, 0, 147574031, 0, 620849157, 0, 433572160, 0, 270718319, 0, 404134457, 0, 242824034, 0, 212675460, 0, 812599908, 0, 693194593, 0, 370922888, 0, 886952955, 0, 700862511, 0, 714683457, 0, 266781052, 0, 254450987, 0, 104223891, 0, 518390975]

def highwayConstruction(n, k):
	if n == 0:
		return 0
	else:
		total = 0
		for i in range(0, k + 1):
			total = (total + C(k + 1, i) * B[i] * pow(n, k + 1 - i, m) % m) % m
		return (pow(k + 1, m - 2, m) * total - 1) % m
q = int(input().strip())
for _ in range(q):
	(n, k) = input().split()
	(n, k) = [int(n), int(k)]
	n -= 1
	result = highwayConstruction(n, k)
	print(result)


bern = [1, 500000005, 833333341, 0, 633333339, 0, 976190485, 0, 633333339, 0, 469696974, 0, 160805862, 0, 833333342, 0, 574509802, 0, 607769484, 0, 269696443, 0, 7252569, 0, 160719282, 0, 834758858, 0, 88793724, 0, 375425307, 0, 458194177, 0, 447972532, 0, 840005835, 0, 147911937, 0, 906304171, 0, 835100855, 0, 790434390, 0, 18465409, 0, 219852826, 0, 729430218, 0, 549724558, 0, 185958893, 0, 966180022, 0, 875441660, 0, 163991022, 0, 122478099, 0, 356692668, 0, 852972500, 0, 843757650, 0, 263617252, 0, 612272568, 0, 983136603, 0, 460777770, 0, 440931647, 0, 1931634, 0, 537844370, 0, 329269021, 0, 664160220, 0, 301809573, 0, 147947308, 0, 209437816, 0, 487053062, 0, 903512931, 0, 38883016, 0, 399980359, 0, 832893605, 0, 137659912, 0, 32046654, 0, 96201969, 0, 272382393, 0, 984809722, 0, 567516997, 0, 277826241, 0, 129450247, 0, 859219181, 0, 495505064, 0, 8707610, 0, 149991844, 0, 197841389, 0, 415837901, 0, 452556555, 0, 255969333, 0, 587269527, 0, 263414781, 0, 832704626, 0, 646359153, 0, 886506266, 0, 485734315, 0, 770784160, 0, 229289872, 0, 784336735, 0, 410524300, 0, 585080214, 0, 141553402, 0, 425223057, 0, 237545850, 0, 63589729, 0, 33858933, 0, 325120530, 0, 395472691, 0, 961112492, 0, 920184514, 0, 418233316, 0, 328311025, 0, 88615861, 0, 818164287, 0, 583547044, 0, 880260567, 0, 227383121, 0, 652754015, 0, 195906609, 0, 143074934, 0, 826044587, 0, 387905283, 0, 604711815, 0, 42021458, 0, 18853119, 0, 261939927, 0, 570870708, 0, 936427877, 0, 22903034, 0, 332187245, 0, 174614373, 0, 11038394, 0, 363254813, 0, 525874981, 0, 658368378, 0, 396296094, 0, 783547564, 0, 20855970, 0, 562367802, 0, 949243780, 0, 211426253, 0, 798316326, 0, 2189158, 0, 549188555, 0, 65168462, 0, 558688513, 0, 614620286, 0, 597722193, 0, 560494311, 0, 673146368, 0, 51251074, 0, 481381363, 0, 701221794, 0, 610905740, 0, 538953990, 0, 735130715, 0, 122194196, 0, 840631161, 0, 315715642, 0, 476095583, 0, 89037894, 0, 197626168, 0, 379851231, 0, 352939984, 0, 1603881, 0, 495686568, 0, 452061366, 0, 22791554, 0, 467084765, 0, 112929067, 0, 26339868, 0, 641824014, 0, 151097054, 0, 27572593, 0, 128712039, 0, 336837738, 0, 136194315, 0, 827051682, 0, 733043040, 0, 940867749, 0, 601253373, 0, 77767278, 0, 414299962, 0, 932037775, 0, 738226723, 0, 239077453, 0, 393853968, 0, 722937698, 0, 91409035, 0, 545345048, 0, 114641356, 0, 148877819, 0, 262317365, 0, 250818962, 0, 921863573, 0, 594138284, 0, 216245249, 0, 268198006, 0, 644235673, 0, 45020701, 0, 15197600, 0, 932257660, 0, 233031406, 0, 893606130, 0, 102728268, 0, 844873407, 0, 402162002, 0, 818789428, 0, 29315973, 0, 246877693, 0, 786369190, 0, 190539628, 0, 650370482, 0, 336782181, 0, 307008561, 0, 182715307, 0, 32544774, 0, 199166544, 0, 936317371, 0, 472944157, 0, 996413699, 0, 308540076, 0, 724760508, 0, 278710238, 0, 728549643, 0, 895187549, 0, 597018742, 0, 891332152, 0, 213314275, 0, 232858337, 0, 769598130, 0, 60714296, 0, 513821745, 0, 334412618, 0, 355998556, 0, 155515182, 0, 272958997, 0, 91080539, 0, 289948741, 0, 18208039, 0, 228396089, 0, 685375239, 0, 932013571, 0, 354972820, 0, 142772925, 0, 327077220, 0, 147126894, 0, 545255853, 0, 326621095, 0, 150434414, 0, 41482011, 0, 669751880, 0, 517959223, 0, 39900214, 0, 101166409, 0, 590690618, 0, 455010719, 0, 605684678, 0, 317918217, 0, 211140566, 0, 435382484, 0, 401548394, 0, 598150259, 0, 526705503, 0, 214208303, 0, 973980798, 0, 259608707, 0, 651883296, 0, 640931689, 0, 709670733, 0, 845424175, 0, 910642853, 0, 117887071, 0, 940539107, 0, 447181503, 0, 775851453, 0, 798595153, 0, 646557270, 0, 598371650, 0, 182121197, 0, 216655153, 0, 233674960, 0, 348110444, 0, 969342628, 0, 941227791, 0, 927291817, 0, 548282982, 0, 35494838, 0, 193345727, 0, 634083526, 0, 848413421, 0, 692263441, 0, 141039063, 0, 420990465, 0, 99968958, 0, 885427102, 0, 974652496, 0, 710104495, 0, 758887858, 0, 657847149, 0, 905536919, 0, 138925594, 0, 961365471, 0, 792067907, 0, 830174595, 0, 887505348, 0, 856653405, 0, 66520656, 0, 464436811, 0, 931952940, 0, 183318987, 0, 89044938, 0, 470198525, 0, 100406774, 0, 2440362, 0, 314128474, 0, 443702464, 0, 253825927, 0, 458301637, 0, 517281429, 0, 216517109, 0, 115148439, 0, 352788208, 0, 524532489, 0, 731457312, 0, 867734240, 0, 702581780, 0, 384432913, 0, 998018408, 0, 799667103, 0, 766683031, 0, 255467277, 0, 769679929, 0, 446799771, 0, 506785884, 0, 90367510, 0, 810460783, 0, 390906268, 0, 739257138, 0, 173415006, 0, 188140175, 0, 540061588, 0, 567270286, 0, 424512513, 0, 502150529, 0, 213408829, 0, 413161595, 0, 961560788, 0, 510494972, 0, 838316082, 0, 879558681, 0, 830705431, 0, 591747767, 0, 237101735, 0, 140378135, 0, 852001724, 0, 331668928, 0, 708252241, 0, 68662461, 0, 182555116, 0, 893538359, 0, 936149439, 0, 951194459, 0, 486306514, 0, 271650811, 0, 699214099, 0, 765695912, 0, 19806886, 0, 205867235, 0, 580303862, 0, 31389524, 0, 219423408, 0, 665425392, 0, 799852916, 0, 744435881, 0, 762868613, 0, 310465177, 0, 526023846, 0, 658432441, 0, 742149662, 0, 110910902, 0, 258750411, 0, 409162808, 0, 977047796, 0, 43894115, 0, 480488643, 0, 268465155, 0, 100559602, 0, 867519227, 0, 633379197, 0, 98138438, 0, 916305323, 0, 103527234, 0, 695952670, 0, 51702511, 0, 697247040, 0, 269625520, 0, 512484589, 0, 959771857, 0, 139799501, 0, 182818844, 0, 360880892, 0, 676601375, 0, 571409550, 0, 423527592, 0, 998937450, 0, 911882358, 0, 357372431, 0, 569826883, 0, 927762812, 0, 789489021, 0, 941796576, 0, 176041796, 0, 72554256, 0, 301167323, 0, 13654611, 0, 452813689, 0, 51503670, 0, 762831889, 0, 585781233, 0, 121672429, 0, 305331100, 0, 967289676, 0, 154103581, 0, 257678198, 0, 977205795, 0, 980551098, 0, 223350161, 0, 894968118, 0, 917907055, 0, 808738276, 0, 937225992, 0, 468349251, 0, 940092683, 0, 30717348, 0, 712135863, 0, 612214371, 0, 200486087, 0, 936406892, 0, 100110001, 0, 427337831, 0, 945651565, 0, 236598252, 0, 690549125, 0, 394737961, 0, 776706329, 0, 299478746, 0, 658529836, 0, 307757330, 0, 566747663, 0, 710125911, 0, 827130658, 0, 9983955, 0, 323916365, 0, 607915625, 0, 685905468, 0, 972001040, 0, 682676454, 0, 310811738, 0, 774922757, 0, 644321926, 0, 512199688, 0, 643906074, 0, 46604419, 0, 857891194, 0, 529476487, 0, 909815091, 0, 734569750, 0, 169167645, 0, 574820238, 0, 181574243, 0, 395929881, 0, 329346463, 0, 236503503, 0, 481065962, 0, 660068394, 0, 39488967, 0, 767760914, 0, 846703781, 0, 131607844, 0, 31944430, 0, 57414656, 0, 103890805, 0, 262746099, 0, 414410559, 0, 887714003, 0, 318008553, 0, 264525958, 0, 313716146, 0, 417633607, 0, 298841184, 0, 773043888, 0, 111856336, 0, 863238900, 0, 906822925, 0, 696923996, 0, 114496374, 0, 434214180, 0, 200788426, 0, 428710692, 0, 644886298, 0, 520452372, 0, 337637872, 0, 113445988, 0, 647989717, 0, 17926007, 0, 750915521, 0, 147574031, 0, 620849157, 0, 433572160, 0, 270718319, 0, 404134457, 0, 242824034, 0, 212675460, 0, 812599908, 0, 693194593, 0, 370922888, 0, 886952955, 0, 700862511, 0, 714683457, 0, 266781052, 0, 254450987, 0, 104223891, 0]
MOD = 1000000009
pas = [1] * 1005
for i in range(2, 1005):
	pas[i] = (MOD - MOD // i) * pas[MOD % i] % MOD
a = int(input())
for _ in range(a):
	(n, k) = map(int, input().strip().split())
	n -= 1
	if n == 0:
		print(0)
		continue
	k += 1
	tmp = 1
	ans = n - (k == 1)
	for i in range(1, k):
		tmp = tmp * (k - i + 1) * pas[i] % MOD
		ans = (ans + tmp * bern[i]) * n % MOD
	print((ans * pas[k] % MOD - 1) % MOD)


import sys
from fractions import Fraction as Fr
import json
from math import gcd
from multiprocessing import Pool
n_terms = 1100
M = int(1000000000.0 + 9)
b_mod_M = [1, 500000005, 833333341, 0, 633333339, 0, 976190485, 0, 633333339, 0, 469696974, 0, 160805862, 0, 833333342, 0, 574509802, 0, 607769484, 0, 269696443, 0, 7252569, 0, 160719282, 0, 834758858, 0, 88793724, 0, 375425307, 0, 458194177, 0, 447972532, 0, 840005835, 0, 147911937, 0, 906304171, 0, 835100855, 0, 790434390, 0, 18465409, 0, 219852826, 0, 729430218, 0, 549724558, 0, 185958893, 0, 966180022, 0, 875441660, 0, 163991022, 0, 122478099, 0, 356692668, 0, 852972500, 0, 843757650, 0, 263617252, 0, 612272568, 0, 983136603, 0, 460777770, 0, 440931647, 0, 1931634, 0, 537844370, 0, 329269021, 0, 664160220, 0, 301809573, 0, 147947308, 0, 209437816, 0, 487053062, 0, 903512931, 0, 38883016, 0, 399980359, 0, 832893605, 0, 137659912, 0, 32046654, 0, 96201969, 0, 272382393, 0, 984809722, 0, 567516997, 0, 277826241, 0, 129450247, 0, 859219181, 0, 495505064, 0, 8707610, 0, 149991844, 0, 197841389, 0, 415837901, 0, 452556555, 0, 255969333, 0, 587269527, 0, 263414781, 0, 832704626, 0, 646359153, 0, 886506266, 0, 485734315, 0, 770784160, 0, 229289872, 0, 784336735, 0, 410524300, 0, 585080214, 0, 141553402, 0, 425223057, 0, 237545850, 0, 63589729, 0, 33858933, 0, 325120530, 0, 395472691, 0, 961112492, 0, 920184514, 0, 418233316, 0, 328311025, 0, 88615861, 0, 818164287, 0, 583547044, 0, 880260567, 0, 227383121, 0, 652754015, 0, 195906609, 0, 143074934, 0, 826044587, 0, 387905283, 0, 604711815, 0, 42021458, 0, 18853119, 0, 261939927, 0, 570870708, 0, 936427877, 0, 22903034, 0, 332187245, 0, 174614373, 0, 11038394, 0, 363254813, 0, 525874981, 0, 658368378, 0, 396296094, 0, 783547564, 0, 20855970, 0, 562367802, 0, 949243780, 0, 211426253, 0, 798316326, 0, 2189158, 0, 549188555, 0, 65168462, 0, 558688513, 0, 614620286, 0, 597722193, 0, 560494311, 0, 673146368, 0, 51251074, 0, 481381363, 0, 701221794, 0, 610905740, 0, 538953990, 0, 735130715, 0, 122194196, 0, 840631161, 0, 315715642, 0, 476095583, 0, 89037894, 0, 197626168, 0, 379851231, 0, 352939984, 0, 1603881, 0, 495686568, 0, 452061366, 0, 22791554, 0, 467084765, 0, 112929067, 0, 26339868, 0, 641824014, 0, 151097054, 0, 27572593, 0, 128712039, 0, 336837738, 0, 136194315, 0, 827051682, 0, 733043040, 0, 940867749, 0, 601253373, 0, 77767278, 0, 414299962, 0, 932037775, 0, 738226723, 0, 239077453, 0, 393853968, 0, 722937698, 0, 91409035, 0, 545345048, 0, 114641356, 0, 148877819, 0, 262317365, 0, 250818962, 0, 921863573, 0, 594138284, 0, 216245249, 0, 268198006, 0, 644235673, 0, 45020701, 0, 15197600, 0, 932257660, 0, 233031406, 0, 893606130, 0, 102728268, 0, 844873407, 0, 402162002, 0, 818789428, 0, 29315973, 0, 246877693, 0, 786369190, 0, 190539628, 0, 650370482, 0, 336782181, 0, 307008561, 0, 182715307, 0, 32544774, 0, 199166544, 0, 936317371, 0, 472944157, 0, 996413699, 0, 308540076, 0, 724760508, 0, 278710238, 0, 728549643, 0, 895187549, 0, 597018742, 0, 891332152, 0, 213314275, 0, 232858337, 0, 769598130, 0, 60714296, 0, 513821745, 0, 334412618, 0, 355998556, 0, 155515182, 0, 272958997, 0, 91080539, 0, 289948741, 0, 18208039, 0, 228396089, 0, 685375239, 0, 932013571, 0, 354972820, 0, 142772925, 0, 327077220, 0, 147126894, 0, 545255853, 0, 326621095, 0, 150434414, 0, 41482011, 0, 669751880, 0, 517959223, 0, 39900214, 0, 101166409, 0, 590690618, 0, 455010719, 0, 605684678, 0, 317918217, 0, 211140566, 0, 435382484, 0, 401548394, 0, 598150259, 0, 526705503, 0, 214208303, 0, 973980798, 0, 259608707, 0, 651883296, 0, 640931689, 0, 709670733, 0, 845424175, 0, 910642853, 0, 117887071, 0, 940539107, 0, 447181503, 0, 775851453, 0, 798595153, 0, 646557270, 0, 598371650, 0, 182121197, 0, 216655153, 0, 233674960, 0, 348110444, 0, 969342628, 0, 941227791, 0, 927291817, 0, 548282982, 0, 35494838, 0, 193345727, 0, 634083526, 0, 848413421, 0, 692263441, 0, 141039063, 0, 420990465, 0, 99968958, 0, 885427102, 0, 974652496, 0, 710104495, 0, 758887858, 0, 657847149, 0, 905536919, 0, 138925594, 0, 961365471, 0, 792067907, 0, 830174595, 0, 887505348, 0, 856653405, 0, 66520656, 0, 464436811, 0, 931952940, 0, 183318987, 0, 89044938, 0, 470198525, 0, 100406774, 0, 2440362, 0, 314128474, 0, 443702464, 0, 253825927, 0, 458301637, 0, 517281429, 0, 216517109, 0, 115148439, 0, 352788208, 0, 524532489, 0, 731457312, 0, 867734240, 0, 702581780, 0, 384432913, 0, 998018408, 0, 799667103, 0, 766683031, 0, 255467277, 0, 769679929, 0, 446799771, 0, 506785884, 0, 90367510, 0, 810460783, 0, 390906268, 0, 739257138, 0, 173415006, 0, 188140175, 0, 540061588, 0, 567270286, 0, 424512513, 0, 502150529, 0, 213408829, 0, 413161595, 0, 961560788, 0, 510494972, 0, 838316082, 0, 879558681, 0, 830705431, 0, 591747767, 0, 237101735, 0, 140378135, 0, 852001724, 0, 331668928, 0, 708252241, 0, 68662461, 0, 182555116, 0, 893538359, 0, 936149439, 0, 951194459, 0, 486306514, 0, 271650811, 0, 699214099, 0, 765695912, 0, 19806886, 0, 205867235, 0, 580303862, 0, 31389524, 0, 219423408, 0, 665425392, 0, 799852916, 0, 744435881, 0, 762868613, 0, 310465177, 0, 526023846, 0, 658432441, 0, 742149662, 0, 110910902, 0, 258750411, 0, 409162808, 0, 977047796, 0, 43894115, 0, 480488643, 0, 268465155, 0, 100559602, 0, 867519227, 0, 633379197, 0, 98138438, 0, 916305323, 0, 103527234, 0, 695952670, 0, 51702511, 0, 697247040, 0, 269625520, 0, 512484589, 0, 959771857, 0, 139799501, 0, 182818844, 0, 360880892, 0, 676601375, 0, 571409550, 0, 423527592, 0, 998937450, 0, 911882358, 0, 357372431, 0, 569826883, 0, 927762812, 0, 789489021, 0, 941796576, 0, 176041796, 0, 72554256, 0, 301167323, 0, 13654611, 0, 452813689, 0, 51503670, 0, 762831889, 0, 585781233, 0, 121672429, 0, 305331100, 0, 967289676, 0, 154103581, 0, 257678198, 0, 977205795, 0, 980551098, 0, 223350161, 0, 894968118, 0, 917907055, 0, 808738276, 0, 937225992, 0, 468349251, 0, 940092683, 0, 30717348, 0, 712135863, 0, 612214371, 0, 200486087, 0, 936406892, 0, 100110001, 0, 427337831, 0, 945651565, 0, 236598252, 0, 690549125, 0, 394737961, 0, 776706329, 0, 299478746, 0, 658529836, 0, 307757330, 0, 566747663, 0, 710125911, 0, 827130658, 0, 9983955, 0, 323916365, 0, 607915625, 0, 685905468, 0, 972001040, 0, 682676454, 0, 310811738, 0, 774922757, 0, 644321926, 0, 512199688, 0, 643906074, 0, 46604419, 0, 857891194, 0, 529476487, 0, 909815091, 0, 734569750, 0, 169167645, 0, 574820238, 0, 181574243, 0, 395929881, 0, 329346463, 0, 236503503, 0, 481065962, 0, 660068394, 0, 39488967, 0, 767760914, 0, 846703781, 0, 131607844, 0, 31944430, 0, 57414656, 0, 103890805, 0, 262746099, 0, 414410559, 0, 887714003, 0, 318008553, 0, 264525958, 0, 313716146, 0, 417633607, 0, 298841184, 0, 773043888, 0, 111856336, 0, 863238900, 0, 906822925, 0, 696923996, 0, 114496374, 0, 434214180, 0, 200788426, 0, 428710692, 0, 644886298, 0, 520452372, 0, 337637872, 0, 113445988, 0, 647989717, 0, 17926007, 0, 750915521, 0, 147574031, 0, 620849157, 0, 433572160, 0, 270718319, 0, 404134457, 0, 242824034, 0, 212675460, 0, 812599908, 0, 693194593, 0, 370922888, 0, 886952955, 0, 700862511, 0, 714683457, 0, 266781052, 0, 254450987, 0, 104223891, 0, 518390975, 0, 347144478, 0, 82841519, 0, 745926148, 0, 603831134, 0, 6428086, 0, 448129469, 0, 939040483, 0, 952221912, 0, 222533518, 0, 752979497, 0, 766363324, 0, 416624647, 0, 344930019, 0, 848056611, 0, 344690856, 0, 99963570, 0, 909972835, 0, 989979700, 0, 250407549, 0, 137957501, 0, 204296838, 0, 242702451, 0, 473503294, 0, 547166809, 0, 108281501, 0, 740956245, 0, 588942381, 0, 382317236, 0, 299630901, 0, 763838434, 0, 774761519, 0, 249342382, 0, 876897409, 0, 769040123, 0, 933750278, 0, 812649723, 0, 641530241, 0, 915557964, 0, 257975945, 0, 717483912, 0, 509258762, 0, 759013101, 0, 14599791, 0, 50782729, 0, 955845965, 0, 799485933, 0, 277300027, 0, 975169431, 0]
factorial = [1]
for i1 in range(1, n_terms):
	factorial.append(factorial[-1] * i1 % M)

def count_factorial(n, p):
	output = 0
	while n >= p:
		output += n / p
		n /= p
	return output

def inverse(n, p):
	return pow(n, p - 2, p)

def binom_coeff(n, k, p):
	if count_factorial(n, p) > count_factorial(k, p) + count_factorial(n - k, p):
		return 0
	return factorial[n] * (inverse(factorial[k], p) * inverse(factorial[n - k], p) % p) % p

def brute_force(n, k):
	output = 0
	for l in range(1, n):
		output += pow(l, k, M)
		output %= M
	output = (output - 1) % M
	return output

def bernoulli_soln(n, k):
	if n == 1:
		return 0
	n_m_1 = n - 1
	output = 0
	for i1 in range(k + 1):
		term = binom_coeff(k, i1, M)
		if term == 0:
			continue
		term = term * b_mod_M[k - i1] % M
		term = term * pow(n_m_1, i1 + 1, M) % M
		term = term * inverse(i1 + 1, M) % M
		output = (output + term) % M
	return (output - 1) % M
q = int(input().strip())
for a0 in range(q):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	result = bernoulli_soln(n, k)
	print(result)


from itertools import chain, product, accumulate
from math import sqrt, floor, ceil, log, log2
from copy import copy, deepcopy
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heapify
from operator import itemgetter
from functools import reduce
from string import ascii_lowercase, ascii_uppercase
gi = lambda : int(input())
gis = lambda : list(map(int, input().split()))
gs = lambda : input()
inf = float('inf')
MOD = 10 ** 9 + 9
MAX_K = 1010
BERNOULLI = [1, 500000004, 833333341, 0, 633333339, 0, 976190485, 0, 633333339, 0, 469696974, 0, 160805862, 0, 833333342, 0, 574509802, 0, 607769484, 0, 269696443, 0, 7252569, 0, 160719282, 0, 834758858, 0, 88793724, 0, 375425307, 0, 458194177, 0, 447972532, 0, 840005835, 0, 147911937, 0, 906304171, 0, 835100855, 0, 790434390, 0, 18465409, 0, 219852826, 0, 729430218, 0, 549724558, 0, 185958893, 0, 966180022, 0, 875441660, 0, 163991022, 0, 122478099, 0, 356692668, 0, 852972500, 0, 843757650, 0, 263617252, 0, 612272568, 0, 983136603, 0, 460777770, 0, 440931647, 0, 1931634, 0, 537844370, 0, 329269021, 0, 664160220, 0, 301809573, 0, 147947308, 0, 209437816, 0, 487053062, 0, 903512931, 0, 38883016, 0, 399980359, 0, 832893605, 0, 137659912, 0, 32046654, 0, 96201969, 0, 272382393, 0, 984809722, 0, 567516997, 0, 277826241, 0, 129450247, 0, 859219181, 0, 495505064, 0, 8707610, 0, 149991844, 0, 197841389, 0, 415837901, 0, 452556555, 0, 255969333, 0, 587269527, 0, 263414781, 0, 832704626, 0, 646359153, 0, 886506266, 0, 485734315, 0, 770784160, 0, 229289872, 0, 784336735, 0, 410524300, 0, 585080214, 0, 141553402, 0, 425223057, 0, 237545850, 0, 63589729, 0, 33858933, 0, 325120530, 0, 395472691, 0, 961112492, 0, 920184514, 0, 418233316, 0, 328311025, 0, 88615861, 0, 818164287, 0, 583547044, 0, 880260567, 0, 227383121, 0, 652754015, 0, 195906609, 0, 143074934, 0, 826044587, 0, 387905283, 0, 604711815, 0, 42021458, 0, 18853119, 0, 261939927, 0, 570870708, 0, 936427877, 0, 22903034, 0, 332187245, 0, 174614373, 0, 11038394, 0, 363254813, 0, 525874981, 0, 658368378, 0, 396296094, 0, 783547564, 0, 20855970, 0, 562367802, 0, 949243780, 0, 211426253, 0, 798316326, 0, 2189158, 0, 549188555, 0, 65168462, 0, 558688513, 0, 614620286, 0, 597722193, 0, 560494311, 0, 673146368, 0, 51251074, 0, 481381363, 0, 701221794, 0, 610905740, 0, 538953990, 0, 735130715, 0, 122194196, 0, 840631161, 0, 315715642, 0, 476095583, 0, 89037894, 0, 197626168, 0, 379851231, 0, 352939984, 0, 1603881, 0, 495686568, 0, 452061366, 0, 22791554, 0, 467084765, 0, 112929067, 0, 26339868, 0, 641824014, 0, 151097054, 0, 27572593, 0, 128712039, 0, 336837738, 0, 136194315, 0, 827051682, 0, 733043040, 0, 940867749, 0, 601253373, 0, 77767278, 0, 414299962, 0, 932037775, 0, 738226723, 0, 239077453, 0, 393853968, 0, 722937698, 0, 91409035, 0, 545345048, 0, 114641356, 0, 148877819, 0, 262317365, 0, 250818962, 0, 921863573, 0, 594138284, 0, 216245249, 0, 268198006, 0, 644235673, 0, 45020701, 0, 15197600, 0, 932257660, 0, 233031406, 0, 893606130, 0, 102728268, 0, 844873407, 0, 402162002, 0, 818789428, 0, 29315973, 0, 246877693, 0, 786369190, 0, 190539628, 0, 650370482, 0, 336782181, 0, 307008561, 0, 182715307, 0, 32544774, 0, 199166544, 0, 936317371, 0, 472944157, 0, 996413699, 0, 308540076, 0, 724760508, 0, 278710238, 0, 728549643, 0, 895187549, 0, 597018742, 0, 891332152, 0, 213314275, 0, 232858337, 0, 769598130, 0, 60714296, 0, 513821745, 0, 334412618, 0, 355998556, 0, 155515182, 0, 272958997, 0, 91080539, 0, 289948741, 0, 18208039, 0, 228396089, 0, 685375239, 0, 932013571, 0, 354972820, 0, 142772925, 0, 327077220, 0, 147126894, 0, 545255853, 0, 326621095, 0, 150434414, 0, 41482011, 0, 669751880, 0, 517959223, 0, 39900214, 0, 101166409, 0, 590690618, 0, 455010719, 0, 605684678, 0, 317918217, 0, 211140566, 0, 435382484, 0, 401548394, 0, 598150259, 0, 526705503, 0, 214208303, 0, 973980798, 0, 259608707, 0, 651883296, 0, 640931689, 0, 709670733, 0, 845424175, 0, 910642853, 0, 117887071, 0, 940539107, 0, 447181503, 0, 775851453, 0, 798595153, 0, 646557270, 0, 598371650, 0, 182121197, 0, 216655153, 0, 233674960, 0, 348110444, 0, 969342628, 0, 941227791, 0, 927291817, 0, 548282982, 0, 35494838, 0, 193345727, 0, 634083526, 0, 848413421, 0, 692263441, 0, 141039063, 0, 420990465, 0, 99968958, 0, 885427102, 0, 974652496, 0, 710104495, 0, 758887858, 0, 657847149, 0, 905536919, 0, 138925594, 0, 961365471, 0, 792067907, 0, 830174595, 0, 887505348, 0, 856653405, 0, 66520656, 0, 464436811, 0, 931952940, 0, 183318987, 0, 89044938, 0, 470198525, 0, 100406774, 0, 2440362, 0, 314128474, 0, 443702464, 0, 253825927, 0, 458301637, 0, 517281429, 0, 216517109, 0, 115148439, 0, 352788208, 0, 524532489, 0, 731457312, 0, 867734240, 0, 702581780, 0, 384432913, 0, 998018408, 0, 799667103, 0, 766683031, 0, 255467277, 0, 769679929, 0, 446799771, 0, 506785884, 0, 90367510, 0, 810460783, 0, 390906268, 0, 739257138, 0, 173415006, 0, 188140175, 0, 540061588, 0, 567270286, 0, 424512513, 0, 502150529, 0, 213408829, 0, 413161595, 0, 961560788, 0, 510494972, 0, 838316082, 0, 879558681, 0, 830705431, 0, 591747767, 0, 237101735, 0, 140378135, 0, 852001724, 0, 331668928, 0, 708252241, 0, 68662461, 0, 182555116, 0, 893538359, 0, 936149439, 0, 951194459, 0, 486306514, 0, 271650811, 0, 699214099, 0, 765695912, 0, 19806886, 0, 205867235, 0, 580303862, 0, 31389524, 0, 219423408, 0, 665425392, 0, 799852916, 0, 744435881, 0, 762868613, 0, 310465177, 0, 526023846, 0, 658432441, 0, 742149662, 0, 110910902, 0, 258750411, 0, 409162808, 0, 977047796, 0, 43894115, 0, 480488643, 0, 268465155, 0, 100559602, 0, 867519227, 0, 633379197, 0, 98138438, 0, 916305323, 0, 103527234, 0, 695952670, 0, 51702511, 0, 697247040, 0, 269625520, 0, 512484589, 0, 959771857, 0, 139799501, 0, 182818844, 0, 360880892, 0, 676601375, 0, 571409550, 0, 423527592, 0, 998937450, 0, 911882358, 0, 357372431, 0, 569826883, 0, 927762812, 0, 789489021, 0, 941796576, 0, 176041796, 0, 72554256, 0, 301167323, 0, 13654611, 0, 452813689, 0, 51503670, 0, 762831889, 0, 585781233, 0, 121672429, 0, 305331100, 0, 967289676, 0, 154103581, 0, 257678198, 0, 977205795, 0, 980551098, 0, 223350161, 0, 894968118, 0, 917907055, 0, 808738276, 0, 937225992, 0, 468349251, 0, 940092683, 0, 30717348, 0, 712135863, 0, 612214371, 0, 200486087, 0, 936406892, 0, 100110001, 0, 427337831, 0, 945651565, 0, 236598252, 0, 690549125, 0, 394737961, 0, 776706329, 0, 299478746, 0, 658529836, 0, 307757330, 0, 566747663, 0, 710125911, 0, 827130658, 0, 9983955, 0, 323916365, 0, 607915625, 0, 685905468, 0, 972001040, 0, 682676454, 0, 310811738, 0, 774922757, 0, 644321926, 0, 512199688, 0, 643906074, 0, 46604419, 0, 857891194, 0, 529476487, 0, 909815091, 0, 734569750, 0, 169167645, 0, 574820238, 0, 181574243, 0, 395929881, 0, 329346463, 0, 236503503, 0, 481065962, 0, 660068394, 0, 39488967, 0, 767760914, 0, 846703781, 0, 131607844, 0, 31944430, 0, 57414656, 0, 103890805, 0, 262746099, 0, 414410559, 0, 887714003, 0, 318008553, 0, 264525958, 0, 313716146, 0, 417633607, 0, 298841184, 0, 773043888, 0, 111856336, 0, 863238900, 0, 906822925, 0, 696923996, 0, 114496374, 0, 434214180, 0, 200788426, 0, 428710692, 0, 644886298, 0, 520452372, 0, 337637872, 0, 113445988, 0, 647989717, 0, 17926007, 0, 750915521, 0, 147574031, 0, 620849157, 0, 433572160, 0, 270718319, 0, 404134457, 0, 242824034, 0, 212675460, 0, 812599908, 0, 693194593, 0, 370922888, 0, 886952955, 0, 700862511, 0, 714683457, 0, 266781052, 0, 254450987, 0, 104223891, 0, 518390975, 0, 347144478]
zz = [1 for _ in range(MAX_K + 1)]
for i in range(2, MAX_K + 1):
	zz[i] = zz[MOD % i] * (MOD - MOD // i) % MOD
for _ in range(gi()):
	(n, k) = gis()
	total = n if k + 1 != 1 else n - 1
	coeff = 1
	for j in range(1, k + 1):
		coeff = coeff * (k - j + 2) * zz[j] % MOD
		total = (total + coeff * BERNOULLI[j]) * n % MOD
	print(max(0, total * zz[k + 1] - 1) % MOD)


p = 10 ** 9 + 9
k = 1000
inverse = [None] + [pow(i, p - 2, p) for i in range(1, k + 3)]
binomial = [[1]]
for m in range(1, k + 2):
	a = binomial[m - 1] + [0]
	b = [0] + binomial[m - 1]
	binomial.append([(a[i] + b[i]) % p for i in range(0, m + 1)])
bernoulli = [1] + [0 for _ in range(k + 1)]
for m in range(1, k + 2):
	s = 0
	for j in range(1, m + 1):
		s += inverse[j + 1] * binomial[m][j] % p * bernoulli[m - j] % p
		s %= p
	bernoulli[m] = p - s

def bernoulli_poly(k, x):
	x_pow = [1] + [0] * k
	for m in range(1, k + 1):
		x_pow[m] = x_pow[m - 1] * x % p
	s = 0
	for m in range(k + 1):
		s += binomial[k][m] * bernoulli[k - m] % p * x_pow[m] % p
		s %= p
	return s

def power_sum(k, n):
	return inverse[k + 1] * (bernoulli_poly(k + 1, n + 1) - bernoulli_poly(k + 1, 0)) % p

def highwayConstruction(n, k):
	if n in [1, 2]:
		return 0
	return (power_sum(k, (n - 1) % p) - 1) % p
q = int(input())
for _ in range(q):
	(n, k) = tuple(map(int, input().split()))
	print(highwayConstruction(n, k))


import sys
MAX_K = 1000
MOD = 1000000009

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a):
	(g, x, y) = egcd(a, MOD)
	return x % MOD
pascal = [[1]]
while len(pascal) <= MAX_K + 1:
	n = len(pascal)
	pascal.append(list(map(sum, zip([0] + pascal[-1], pascal[-1] + [0]))))
bernoulli = [1]
while len(bernoulli) <= MAX_K:
	n = len(bernoulli)
	if n == 1:
		bernoulli.append(-modinv(n + 1) % MOD)
	elif n % 2 == 1:
		bernoulli.append(0)
	else:
		x = pascal[n + 1][1] * bernoulli[1]
		x += sum((pascal[n + 1][i] * bernoulli[i] for i in range(0, n, 2)))
		bernoulli.append(-x * modinv(n + 1) % MOD)
T = int(sys.stdin.readline())
hello = p = 0
for _ in range(T):
	(n, K) = list(map(int, sys.stdin.readline().split()))
	if n != 1 and n != 2:
		hello = pow(n, K) + 1
	else:
		hello = 1
	x = sum((pow(-1, i) * pascal[K + 1][i] * bernoulli[i] * pow(n, K + 1 - i, MOD) for i in range(K + 1)))
	p = x * modinv(K + 1) - hello
	print(p % MOD)


import sys

def highwayConstruction(n, k):
	m = 10 ** 9 + 9
	B = [1, 500000005, 833333341, 0, 633333339, 0, 976190485, 0, 633333339, 0, 469696974, 0, 160805862, 0, 833333342, 0, 574509802, 0, 607769484, 0, 269696443, 0, 7252569, 0, 160719282, 0, 834758858, 0, 88793724, 0, 375425307, 0, 458194177, 0, 447972532, 0, 840005835, 0, 147911937, 0, 906304171, 0, 835100855, 0, 790434390, 0, 18465409, 0, 219852826, 0, 729430218, 0, 549724558, 0, 185958893, 0, 966180022, 0, 875441660, 0, 163991022, 0, 122478099, 0, 356692668, 0, 852972500, 0, 843757650, 0, 263617252, 0, 612272568, 0, 983136603, 0, 460777770, 0, 440931647, 0, 1931634, 0, 537844370, 0, 329269021, 0, 664160220, 0, 301809573, 0, 147947308, 0, 209437816, 0, 487053062, 0, 903512931, 0, 38883016, 0, 399980359, 0, 832893605, 0, 137659912, 0, 32046654, 0, 96201969, 0, 272382393, 0, 984809722, 0, 567516997, 0, 277826241, 0, 129450247, 0, 859219181, 0, 495505064, 0, 8707610, 0, 149991844, 0, 197841389, 0, 415837901, 0, 452556555, 0, 255969333, 0, 587269527, 0, 263414781, 0, 832704626, 0, 646359153, 0, 886506266, 0, 485734315, 0, 770784160, 0, 229289872, 0, 784336735, 0, 410524300, 0, 585080214, 0, 141553402, 0, 425223057, 0, 237545850, 0, 63589729, 0, 33858933, 0, 325120530, 0, 395472691, 0, 961112492, 0, 920184514, 0, 418233316, 0, 328311025, 0, 88615861, 0, 818164287, 0, 583547044, 0, 880260567, 0, 227383121, 0, 652754015, 0, 195906609, 0, 143074934, 0, 826044587, 0, 387905283, 0, 604711815, 0, 42021458, 0, 18853119, 0, 261939927, 0, 570870708, 0, 936427877, 0, 22903034, 0, 332187245, 0, 174614373, 0, 11038394, 0, 363254813, 0, 525874981, 0, 658368378, 0, 396296094, 0, 783547564, 0, 20855970, 0, 562367802, 0, 949243780, 0, 211426253, 0, 798316326, 0, 2189158, 0, 549188555, 0, 65168462, 0, 558688513, 0, 614620286, 0, 597722193, 0, 560494311, 0, 673146368, 0, 51251074, 0, 481381363, 0, 701221794, 0, 610905740, 0, 538953990, 0, 735130715, 0, 122194196, 0, 840631161, 0, 315715642, 0, 476095583, 0, 89037894, 0, 197626168, 0, 379851231, 0, 352939984, 0, 1603881, 0, 495686568, 0, 452061366, 0, 22791554, 0, 467084765, 0, 112929067, 0, 26339868, 0, 641824014, 0, 151097054, 0, 27572593, 0, 128712039, 0, 336837738, 0, 136194315, 0, 827051682, 0, 733043040, 0, 940867749, 0, 601253373, 0, 77767278, 0, 414299962, 0, 932037775, 0, 738226723, 0, 239077453, 0, 393853968, 0, 722937698, 0, 91409035, 0, 545345048, 0, 114641356, 0, 148877819, 0, 262317365, 0, 250818962, 0, 921863573, 0, 594138284, 0, 216245249, 0, 268198006, 0, 644235673, 0, 45020701, 0, 15197600, 0, 932257660, 0, 233031406, 0, 893606130, 0, 102728268, 0, 844873407, 0, 402162002, 0, 818789428, 0, 29315973, 0, 246877693, 0, 786369190, 0, 190539628, 0, 650370482, 0, 336782181, 0, 307008561, 0, 182715307, 0, 32544774, 0, 199166544, 0, 936317371, 0, 472944157, 0, 996413699, 0, 308540076, 0, 724760508, 0, 278710238, 0, 728549643, 0, 895187549, 0, 597018742, 0, 891332152, 0, 213314275, 0, 232858337, 0, 769598130, 0, 60714296, 0, 513821745, 0, 334412618, 0, 355998556, 0, 155515182, 0, 272958997, 0, 91080539, 0, 289948741, 0, 18208039, 0, 228396089, 0, 685375239, 0, 932013571, 0, 354972820, 0, 142772925, 0, 327077220, 0, 147126894, 0, 545255853, 0, 326621095, 0, 150434414, 0, 41482011, 0, 669751880, 0, 517959223, 0, 39900214, 0, 101166409, 0, 590690618, 0, 455010719, 0, 605684678, 0, 317918217, 0, 211140566, 0, 435382484, 0, 401548394, 0, 598150259, 0, 526705503, 0, 214208303, 0, 973980798, 0, 259608707, 0, 651883296, 0, 640931689, 0, 709670733, 0, 845424175, 0, 910642853, 0, 117887071, 0, 940539107, 0, 447181503, 0, 775851453, 0, 798595153, 0, 646557270, 0, 598371650, 0, 182121197, 0, 216655153, 0, 233674960, 0, 348110444, 0, 969342628, 0, 941227791, 0, 927291817, 0, 548282982, 0, 35494838, 0, 193345727, 0, 634083526, 0, 848413421, 0, 692263441, 0, 141039063, 0, 420990465, 0, 99968958, 0, 885427102, 0, 974652496, 0, 710104495, 0, 758887858, 0, 657847149, 0, 905536919, 0, 138925594, 0, 961365471, 0, 792067907, 0, 830174595, 0, 887505348, 0, 856653405, 0, 66520656, 0, 464436811, 0, 931952940, 0, 183318987, 0, 89044938, 0, 470198525, 0, 100406774, 0, 2440362, 0, 314128474, 0, 443702464, 0, 253825927, 0, 458301637, 0, 517281429, 0, 216517109, 0, 115148439, 0, 352788208, 0, 524532489, 0, 731457312, 0, 867734240, 0, 702581780, 0, 384432913, 0, 998018408, 0, 799667103, 0, 766683031, 0, 255467277, 0, 769679929, 0, 446799771, 0, 506785884, 0, 90367510, 0, 810460783, 0, 390906268, 0, 739257138, 0, 173415006, 0, 188140175, 0, 540061588, 0, 567270286, 0, 424512513, 0, 502150529, 0, 213408829, 0, 413161595, 0, 961560788, 0, 510494972, 0, 838316082, 0, 879558681, 0, 830705431, 0, 591747767, 0, 237101735, 0, 140378135, 0, 852001724, 0, 331668928, 0, 708252241, 0, 68662461, 0, 182555116, 0, 893538359, 0, 936149439, 0, 951194459, 0, 486306514, 0, 271650811, 0, 699214099, 0, 765695912, 0, 19806886, 0, 205867235, 0, 580303862, 0, 31389524, 0, 219423408, 0, 665425392, 0, 799852916, 0, 744435881, 0, 762868613, 0, 310465177, 0, 526023846, 0, 658432441, 0, 742149662, 0, 110910902, 0, 258750411, 0, 409162808, 0, 977047796, 0, 43894115, 0, 480488643, 0, 268465155, 0, 100559602, 0, 867519227, 0, 633379197, 0, 98138438, 0, 916305323, 0, 103527234, 0, 695952670, 0, 51702511, 0, 697247040, 0, 269625520, 0, 512484589, 0, 959771857, 0, 139799501, 0, 182818844, 0, 360880892, 0, 676601375, 0, 571409550, 0, 423527592, 0, 998937450, 0, 911882358, 0, 357372431, 0, 569826883, 0, 927762812, 0, 789489021, 0, 941796576, 0, 176041796, 0, 72554256, 0, 301167323, 0, 13654611, 0, 452813689, 0, 51503670, 0, 762831889, 0, 585781233, 0, 121672429, 0, 305331100, 0, 967289676, 0, 154103581, 0, 257678198, 0, 977205795, 0, 980551098, 0, 223350161, 0, 894968118, 0, 917907055, 0, 808738276, 0, 937225992, 0, 468349251, 0, 940092683, 0, 30717348, 0, 712135863, 0, 612214371, 0, 200486087, 0, 936406892, 0, 100110001, 0, 427337831, 0, 945651565, 0, 236598252, 0, 690549125, 0, 394737961, 0, 776706329, 0, 299478746, 0, 658529836, 0, 307757330, 0, 566747663, 0, 710125911, 0, 827130658, 0, 9983955, 0, 323916365, 0, 607915625, 0, 685905468, 0, 972001040, 0, 682676454, 0, 310811738, 0, 774922757, 0, 644321926, 0, 512199688, 0, 643906074, 0, 46604419, 0, 857891194, 0, 529476487, 0, 909815091, 0, 734569750, 0, 169167645, 0, 574820238, 0, 181574243, 0, 395929881, 0, 329346463, 0, 236503503, 0, 481065962, 0, 660068394, 0, 39488967, 0, 767760914, 0, 846703781, 0, 131607844, 0, 31944430, 0, 57414656, 0, 103890805, 0, 262746099, 0, 414410559, 0, 887714003, 0, 318008553, 0, 264525958, 0, 313716146, 0, 417633607, 0, 298841184, 0, 773043888, 0, 111856336, 0, 863238900, 0, 906822925, 0, 696923996, 0, 114496374, 0, 434214180, 0, 200788426, 0, 428710692, 0, 644886298, 0, 520452372, 0, 337637872, 0, 113445988, 0, 647989717, 0, 17926007, 0, 750915521, 0, 147574031, 0, 620849157, 0, 433572160, 0, 270718319, 0, 404134457, 0, 242824034, 0, 212675460, 0, 812599908, 0, 693194593, 0, 370922888, 0, 886952955, 0, 700862511, 0, 714683457, 0, 266781052, 0, 254450987, 0, 104223891, 0, 518390975, 0, 347144478, 0, 82841519, 0, 745926148, 0, 603831134]
	N = 1003
	b = [1] * (N + 1)
	for i in range(N - 1):
		b[i + 2] = (m - m // (i + 2)) * b[m % (i + 2)] % m
	k = k + 1
	c = 1
	a = n - 1 - (k == 1)
	for r in range(k - 1):
		c = c * (k - r) * b[r + 1] % m
		a = (a + c * B[r + 1]) * (n - 1) % m
	o = a * b[k] % m - 1
	return o
q = int(input().strip())
for a0 in range(q):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	if n > 1:
		result = highwayConstruction(n, k)
	else:
		result = 0
	print(result)


from math import factorial
from fractions import Fraction
from time import time
startTime = time()

def HCF(x, y):
	while y != 0:
		(x, y) = (min(x, y), max(x, y))
		y %= x
	return x

def findModularInverse(m, n):
	if HCF(m, n) != 1:
		return 'Not coprime.'
	(s, sx, sy, t, tx, ty) = (m, 1, 0, n, 0, 1)
	while True:
		(q, r) = (s // t, s % t)
		(u, ux, uy) = (r, sx - q * tx, sy - q * ty)
		if r == 0:
			(a, b) = (tx, ty)
			break
		else:
			(s, sx, sy, t, tx, ty) = (t, tx, ty, u, ux, uy)
			del q, r, u, ux, uy
	return a % n

def nCr(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r))
pascalsTriangle = []
row = [1]
pascalsTriangle.append(row[:])
for rowIndex in range(1, 1002):
	row = [1] + [row[i] + row[i + 1] for i in range(len(row) - 1)] + [1]
	pascalsTriangle.append(row[:])
bernoulliNumbers = [Fraction(1, 1)]
for rowI in range(1, 1001):
	if rowI >= 3 and rowI % 2 == 1:
		bernoulliNumbers.append(0)
		continue
	pascalTriangleRow = pascalsTriangle[rowI + 1]
	newbernoulliNumber = Fraction(-sum((pascalTriangleRow[i] * bernoulliNumbers[i] for i in range(rowI))), pascalTriangleRow[rowI])
	bernoulliNumbers.append(newbernoulliNumber)
bernoulliNumbers[1] = Fraction(1, 2)
T = int(input())
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	if N == 1:
		print(0)
		continue
	if N == 2:
		print(1)
		continue
	(n, k) = (N - 1, K)
	P = 1000000009
	totalCost = 0
	coefficients = [0 for j in range(0, k + 1 + 1)]
	for j in range(k + 1):
		coefficients[k + 1 - j] = Fraction(1, k + 1) * pascalsTriangle[k + 1][j] * bernoulliNumbers[j]
	powersOfN = [1]
	for i in range(1001):
		powersOfN.append(powersOfN[-1] * n % P)
	totalCost = 0
	for i in range(k + 2):
		coefficient = coefficients[i]
		totalCost += coefficient.numerator * powersOfN[i] * findModularInverse(coefficient.denominator, P)
	totalCost -= 1
	totalCost %= P
	print(totalCost)
import sys
print('Time taken =', time() - startTime, 'seconds', file=sys.stderr)
del sys


import sys
mod = 10 ** 9 + 9
B = [0 for _ in range(1001)]
inv = [i for i in range(10001)]
fac = [i for i in range(10001)]
fac[0] = 1
for i in range(1, 10001):
	inv[i] = pow(i, mod - 2, mod)
for i in range(1, 10001):
	fac[i] = fac[i - 1] * i
	fac[i] %= mod
invfac = fac[:]
for i in range(len(invfac)):
	invfac[i] = pow(invfac[i], mod - 2, mod)

def comb(n, k):
	return fac[n] * invfac[n - k] * invfac[k] % mod
B[0] = 1
B[1] = (mod - 1) * pow(2, mod - 2, mod) % mod
for m in range(2, 1001):
	for k in range(m):
		B[m] -= comb(m, k) * B[k] * inv[m - k + 1] % mod
		B[m] %= mod
B[1] = mod - B[1]

def f(n, p):
	res = 0
	for k in range(p + 1):
		res += comb(p, k) * B[p - k] * pow(n, k + 1, mod) * inv[k + 1] % mod
		res %= mod
	return res

def highwayConstruction(n, k):
	if n <= 2:
		return 0
	return (f(n - 1, k) + mod - 1) % mod
q = int(input().strip())
for a0 in range(q):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	result = highwayConstruction(n, k)
	print(result)


import time
from fractions import Fraction as fr
from math import floor

def euclidean_alg(a, b):
	rm1 = a
	sm1 = 1
	tm1 = 0
	r = b
	s = 0
	t = 1
	while r != 0:
		q = rm1 // r
		temp_r = rm1
		temp_s = sm1
		temp_t = tm1
		rm1 = r
		sm1 = s
		tm1 = t
		r = temp_r - q * rm1
		s = temp_s - q * sm1
		t = temp_t - q * tm1
	return (rm1, sm1, tm1)

def modular_inverse(n, p):
	(r, s, t) = euclidean_alg(n, p)
	return s
modulus = 10 ** 9 + 9

def bernoulli_mod(n, modulus):
	res = []
	A = []
	for m in range(n + 1):
		A.append(modular_inverse(m + 1, modulus))
		for j in range(m, 0, -1):
			A[j - 1] = j * (A[j - 1] - A[j]) % modulus
		res.append(A[0])
	return res
bern = bernoulli_mod(1001, modulus)

def solve(n, k):
	if n <= 2:
		return 0
	ans = 0
	bin = 1
	for j in range(k + 1):
		ans = (ans + bin * bern[j] * pow(n - 1, k + 1 - j, modulus)) % modulus
		bin = bin * (k + 1 - j) * modular_inverse(j + 1, modulus) % modulus
	ans = (ans * modular_inverse(k + 1, modulus) - 1) % modulus
	return ans
q = int(input())
for i in range(q):
	(n, k) = [int(val) for val in input().split()]
	print(solve(n, k))


import time
from fractions import Fraction as fr
from math import floor

def euclidean_alg(a, b):
	rm1 = a
	sm1 = 1
	tm1 = 0
	r = b
	s = 0
	t = 1
	while r != 0:
		q = rm1 // r
		temp_r = rm1
		temp_s = sm1
		temp_t = tm1
		rm1 = r
		sm1 = s
		tm1 = t
		r = temp_r - q * rm1
		s = temp_s - q * sm1
		t = temp_t - q * tm1
	return (rm1, sm1, tm1)

def modular_inverse(n, p):
	(r, s, t) = euclidean_alg(n, p)
	return s
modulus = 10 ** 9 + 9

def bernoulli_mod(n, modulus):
	res = []
	A = []
	for m in range(n + 1):
		A.append(modular_inverse(m + 1, modulus))
		for j in range(m, 0, -1):
			A[j - 1] = j * (A[j - 1] - A[j]) % modulus
		res.append(A[0])
	return res
bern = bernoulli_mod(1001, modulus)

def solve(n, k):
	if n <= 2:
		return 0
	ans = 0
	bin = 1
	for j in range(k + 1):
		ans = (ans + bin * bern[j] * pow(n - 1, k + 1 - j, modulus)) % modulus
		bin = bin * (k + 1 - j) * modular_inverse(j + 1, modulus) % modulus
	ans = (ans * modular_inverse(k + 1, modulus) - 1) % modulus
	return ans
q = int(input())
for i in range(q):
	(n, k) = [int(val) for val in input().split()]
	print(solve(n, k))


import time
from fractions import Fraction as fr
from math import floor

def euclidean_alg(a, b):
	rm1 = a
	sm1 = 1
	tm1 = 0
	r = b
	s = 0
	t = 1
	while r != 0:
		q = rm1 // r
		temp_r = rm1
		temp_s = sm1
		temp_t = tm1
		rm1 = r
		sm1 = s
		tm1 = t
		r = temp_r - q * rm1
		s = temp_s - q * sm1
		t = temp_t - q * tm1
	return (rm1, sm1, tm1)

def modular_inverse(n, p):
	(r, s, t) = euclidean_alg(n, p)
	return s
modulus = 10 ** 9 + 9

def bernoulli_mod(n, modulus):
	res = []
	A = []
	for m in range(n + 1):
		A.append(modular_inverse(m + 1, modulus))
		for j in range(m, 0, -1):
			A[j - 1] = j * (A[j - 1] - A[j]) % modulus
		res.append(A[0])
	return res
bern = bernoulli_mod(1001, modulus)

def solve(n, k):
	if n <= 2:
		return 0
	ans = 0
	bin = 1
	for j in range(k + 1):
		ans = (ans + bin * bern[j] * pow(n - 1, k + 1 - j, modulus)) % modulus
		bin = bin * (k + 1 - j) * modular_inverse(j + 1, modulus) % modulus
	ans = (ans * modular_inverse(k + 1, modulus) - 1) % modulus
	return ans
q = int(input())
for i in range(q):
	(n, k) = [int(val) for val in input().split()]
	print(solve(n, k))


import time
from fractions import Fraction as fr
from math import floor

def euclidean_alg(a, b):
	rm1 = a
	sm1 = 1
	tm1 = 0
	r = b
	s = 0
	t = 1
	while r != 0:
		q = rm1 // r
		temp_r = rm1
		temp_s = sm1
		temp_t = tm1
		rm1 = r
		sm1 = s
		tm1 = t
		r = temp_r - q * rm1
		s = temp_s - q * sm1
		t = temp_t - q * tm1
	return (rm1, sm1, tm1)

def modular_inverse(n, p):
	(r, s, t) = euclidean_alg(n, p)
	return s
modulus = 10 ** 9 + 9

def bernoulli_mod(n, modulus):
	res = []
	A = []
	for m in range(n + 1):
		A.append(modular_inverse(m + 1, modulus))
		for j in range(m, 0, -1):
			A[j - 1] = j * (A[j - 1] - A[j]) % modulus
		res.append(A[0])
	return res
bern = bernoulli_mod(1001, modulus)

def solve(n, k):
	if n <= 2:
		return 0
	ans = 0
	bin = 1
	for j in range(k + 1):
		ans = (ans + bin * bern[j] * pow(n - 1, k + 1 - j, modulus)) % modulus
		bin = bin * (k + 1 - j) * modular_inverse(j + 1, modulus) % modulus
	ans = (ans * modular_inverse(k + 1, modulus) - 1) % modulus
	return ans
q = int(input())
for i in range(q):
	(n, k) = [int(val) for val in input().split()]
	print(solve(n, k))


import time
from fractions import Fraction as fr
from math import floor

def euclidean_alg(a, b):
	rm1 = a
	sm1 = 1
	tm1 = 0
	r = b
	s = 0
	t = 1
	while r != 0:
		q = rm1 // r
		temp_r = rm1
		temp_s = sm1
		temp_t = tm1
		rm1 = r
		sm1 = s
		tm1 = t
		r = temp_r - q * rm1
		s = temp_s - q * sm1
		t = temp_t - q * tm1
	return (rm1, sm1, tm1)

def modular_inverse(n, p):
	(r, s, t) = euclidean_alg(n, p)
	return s
modulus = 10 ** 9 + 9

def bernoulli_mod(n, modulus):
	res = []
	A = []
	for m in range(n + 1):
		A.append(modular_inverse(m + 1, modulus))
		for j in range(m, 0, -1):
			A[j - 1] = j * (A[j - 1] - A[j]) % modulus
		res.append(A[0])
	return res
bern = bernoulli_mod(1001, modulus)

def solve(n, k):
	if n <= 2:
		return 0
	ans = 0
	bin = 1
	for j in range(k + 1):
		ans = (ans + bin * bern[j] * pow(n - 1, k + 1 - j, modulus)) % modulus
		bin = bin * (k + 1 - j) * modular_inverse(j + 1, modulus) % modulus
	ans = (ans * modular_inverse(k + 1, modulus) - 1) % modulus
	return ans
q = int(input())
for i in range(q):
	(n, k) = [int(val) for val in input().split()]
	print(solve(n, k))


import time
from fractions import Fraction as fr
from math import floor

def euclidean_alg(a, b):
	rm1 = a
	sm1 = 1
	tm1 = 0
	r = b
	s = 0
	t = 1
	while r != 0:
		q = rm1 // r
		temp_r = rm1
		temp_s = sm1
		temp_t = tm1
		rm1 = r
		sm1 = s
		tm1 = t
		r = temp_r - q * rm1
		s = temp_s - q * sm1
		t = temp_t - q * tm1
	return (rm1, sm1, tm1)

def modular_inverse(n, p):
	(r, s, t) = euclidean_alg(n, p)
	return s
modulus = 10 ** 9 + 9

def bernoulli_mod(n, modulus):
	res = []
	A = []
	for m in range(n + 1):
		A.append(modular_inverse(m + 1, modulus))
		for j in range(m, 0, -1):
			A[j - 1] = j * (A[j - 1] - A[j]) % modulus
		res.append(A[0])
	return res
bern = bernoulli_mod(1001, modulus)

def solve(n, k):
	if n <= 2:
		return 0
	ans = 0
	bin = 1
	for j in range(k + 1):
		ans = (ans + bin * bern[j] * pow(n - 1, k + 1 - j, modulus)) % modulus
		bin = bin * (k + 1 - j) * modular_inverse(j + 1, modulus) % modulus
	ans = (ans * modular_inverse(k + 1, modulus) - 1) % modulus
	return ans
q = int(input())
for i in range(q):
	(n, k) = [int(val) for val in input().split()]
	print(solve(n, k))


import time
from fractions import Fraction as fr
from math import floor

def euclidean_alg(a, b):
	rm1 = a
	sm1 = 1
	tm1 = 0
	r = b
	s = 0
	t = 1
	while r != 0:
		q = rm1 // r
		temp_r = rm1
		temp_s = sm1
		temp_t = tm1
		rm1 = r
		sm1 = s
		tm1 = t
		r = temp_r - q * rm1
		s = temp_s - q * sm1
		t = temp_t - q * tm1
	return (rm1, sm1, tm1)

def modular_inverse(n, p):
	(r, s, t) = euclidean_alg(n, p)
	return s
modulus = 10 ** 9 + 9

def bernoulli_mod(n, modulus):
	res = []
	A = []
	for m in range(n + 1):
		A.append(modular_inverse(m + 1, modulus))
		for j in range(m, 0, -1):
			A[j - 1] = j * (A[j - 1] - A[j]) % modulus
		res.append(A[0])
	return res
bern = bernoulli_mod(1001, modulus)

def solve(n, k):
	if n <= 2:
		return 0
	ans = 0
	bin = 1
	for j in range(k + 1):
		ans = (ans + bin * bern[j] * pow(n - 1, k + 1 - j, modulus)) % modulus
		bin = bin * (k + 1 - j) * modular_inverse(j + 1, modulus) % modulus
	ans = (ans * modular_inverse(k + 1, modulus) - 1) % modulus
	return ans
q = int(input())
for i in range(q):
	(n, k) = [int(val) for val in input().split()]
	print(solve(n, k))