Spoj Peru

Mario se encontraba jugando con un conjunto S = {1,2,...,n}, y ahora quiere contar
la cantidad de ciertas funciones F cuyo dominio y rango sea S, y cuyo rango incluya a todos
los elementos de S, además estas funciones deben cumplir que si tomamos un
entero x de S y aplicamos la función F a x, un número de veces fijo K, se tenga que el
resultado sea diferente de x. Debes contar la cantidad de estas funciones módulo
10^9 + 7.

Input

La entrada inicia con un entero T (T <= 30)
Siguen T líneas cada una con dos enteros n (n <= 1000), K (K <= 1000)

Output

Una línea con la respuesta para cada caso

Example

Input:
2
2 2
3 2

Output:
0
2