Cerința

Se dau n perechi de numere naturale, m şi k. Pentru fiecare pereche să se afle câte numere naturale de m cifre, formate cu cifrele 1,2,...,k există, astfel încât prin permutarea cifrelor să devină palindromuri.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n perechi de numere naturale m și k, separate prin spații.

Date de ieșire

Programul va afișa pe ecran, pentru fiecare pereche m şi k, numărul cerut modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ m ≤ 1.000.000.000
• 1 ≤ k ≤ 9

Exemplu:

Intrare

4
2 2
3 1
4 3
5 5

Ieșire

2
1
21
1205

Explicație

Numerele de lungime 2, formate cu cifrele 1,2, care pot deveni palindroame prin permutarea cifrelor sunt 11 şi 22.
Numerele de lungime 3, formate cu cifra 1, care pot deveni palindroame prin permutarea cifrelor sunt 111.
Numerele de lungime 4, formate cu cifrele 1,2,3, care pot deveni palindroame prin permutarea cifrelor sunt
1111, 2222, 3333, 1122, 1212, 1221, 2112, 2121, 2211, 1133,1313, 1331, 3113, 3131, 3311, 2233, 2323, 2332, 3223, 3232, 3322.