Borussia Dortmund are a famous football ( soccer ) club from Germany. Apart from their fast-paced style of playing, the thing that makes them unique is the hard to pronounce names of their players ( błaszczykowski , papastathopoulos , großkreutz etc. ).

The team's coach is your friend. He is in a dilemma as he can't decide how to make it easier to call the players by name, during practice sessions. So, you advise him to assign easy names to his players. A name is easy to him if 

1. It consists of only one word. 

2. It consists of only lowercase english letters. 

3. Its length is exactly $N$. 

4. It contains exactly $\mbox{K}$ different letters from the $26$ letters of English alphabet. 

5. At least one of its proper prefixes matches with its proper suffix of same length.

Given, $N$ and $\mbox{K}$ you have to tell him the number of easy names he can choose from modulo $(10^9+9)$.

Note : A prefix $\mbox{P}$ of a name $\mbox{w}$ is proper if, $P\neq W$. Similarly, a suffix $\mbox{S}$ of a name $\mbox{W}$ is proper if, $S\neq W$.

Input Format 

The first line of the input will contain $\mathbf{T}$ ( the number of testcases ).
Each of the next $\mathbf{T}$ lines will contain $2$ space separated integers $N$ and $\mbox{K}$.

Output Format 

For each testcase, output the number of ways the coach can assign names to his players modulo $(10^9+9)$.

Constraints 

$1\leq T\leq10^5$ 

$1\leq N\leq10^5$ 

$1\leq K\leq26$

Sample Input #1

3
1 1
2 1
4 2

Sample Output #1

0  
26 
2600  

Sample Input #2

5  
2 2
5 1
3 2
6 2
1 3

Sample Output #2

0
26
650
13650
0

Source: hackerrank | Difficulty: HARD
Tags: Dynamic programming


Solutions:
import math
MODULO = 10 ** 9 + 9
MAXN = 10 ** 5 + 5

def plus(x, y):
	return (x + y) % MODULO

def minus(x, y):
	return (x - y) % MODULO

def times(x, y):
	return x * y % MODULO

def power(x, y):
	return pow(x, y, MODULO)

def nCr(n, r):
	return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
minlen = [[0 for y in range(27)] for x in range(MAXN)]
answer = [[0 for y in range(27)] for x in range(MAXN)]
for k in range(1, 26 + 1):
	carry = 0
	kto = 1
	for i in range(1, MAXN):
		kto = times(kto, k)
		carry = times(carry, k)
		if i == 1:
			minlen[i][k] = k
			answer[i][k] = 0
		else:
			if i % 2 == 0:
				carry = plus(carry, minlen[i // 2][k])
			minlen[i][k] = minus(kto, carry)
			answer[i][k] = carry
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	tmp = answer[N][K]
	for j in range(1, K):
		if (K - j) % 2 == 1:
			tmp = minus(tmp, times(answer[N][j], nCr(K, j)))
		else:
			tmp = plus(tmp, times(answer[N][j], nCr(K, j)))
	tmp = times(tmp, nCr(26, K))
	print(tmp)


def func():
	MOD = 10 ** 9 + 9
	Max = 10 ** 5 + 1
	nCr = [[1]]
	for n in range(1, 27):
		m = [1]
		for k in range(1, n):
			m.append(nCr[-1][k] + nCr[-1][k - 1])
		m.append(1)
		nCr.append(m)
	DP = [[]]
	for k in range(1, 27):
		FDP = [1]
		for i in range(1, Max):
			temp = FDP[-1] * k
			if i % 2 == 0:
				temp = temp - FDP[i // 2]
			FDP.append(temp % MOD)
		DP.append(FDP)
	for t in range(int(input())):
		(N, K) = map(int, input().split())
		G = [0]
		for i in range(1, K + 1):
			G.append(pow(i, N, MOD) - DP[i][N] - sum((G[j] * nCr[i][j] for j in range(1, i))) % MOD)
		print(G[-1] * nCr[26][K] % MOD)
func()