DORTMUND - Dortmund Dilemma

Borussia Dortmund is a famous football (soccer) club from Germany. Apart from their fast 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 advised him to assign easy names to his players. A name is easy to him if

  1. It consists of only lowercase English letters.
  2. Its length is exactly N.
  3. It contains exactly K different letters from the 26 letters of English alphabet.
  4. At least one of its proper prefixes matches with its proper suffix of same length.

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

Note : A prefix P of a name W is proper if, P ≠ W. Similarly, a suffix S of a name W is proper if, S ≠ W.

Input

The first line of the input will contain T ( the number of testcases ).
Each of the next T lines will contain two space separated integers N and K.

Output

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

Constraints

1 ≤ T ≤ 105 
1 ≤ N ≤ 105   
1 ≤ K ≤ 26

Example

Input:
8
1 1
2 1
4 2
2 2
5 1
3 2
6 2
1 3 Output: 0
26
2600
0
26
650
13650
0

Added by:Bidhan
Date:2014-08-03
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: WHITESPACE
Resource:Own problem from HackerRank

hide comments
2024-03-14 13:20:54 Sushovan Sen
Wow! easy names with length 10^9
2016-02-14 15:21:21 Siddharth Singh
Solved It After A Month, Read A Lot To Solve Thing. Finalllyyyy!!!!
BVB09 Always <3
2015-03-11 11:22:56 (Tjandra Satria Gunawan)(曾毅昆)
Warning: unusual modulo 10^9+9 not 10^9+7, cost me many WA (>_<)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.