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
.