Para atraer clientes, el dueño de una tienda decidió encargar un letrero de neón especial para colocarlo delante de la tienda. El letrero consta de varios componentes con forma de escalera. Cada uno puede representarse mediante un grafo escalera $L_n$, un grafo plano no dirigido con $2n$ vértices y $3n-2$ aristas. Cada vértice representa una bombilla y cada arista un cable que conecta dos bombillas. El grafo escalera es el producto cartesiano de dos grafos camino, uno de los cuales tiene una sola arista: $L_n=P_n\times P_2$, donde $P_n$ es un camino de $n$ vértices. La figura 1 muestra $L_6$. El armazón principal que sostiene $k$ componentes es un polígono regular de $k$ lados.

Figura 1: $L_6$.

Cada lado del polígono regular se combina con la arista superior de $L_n$. La figura 2 muestra el caso $k=3$, $n=4$, y la figura 3 el caso $k=4$, $n=3$. Para facilitar la descripción, el letrero se representa por un grafo $G=(V,E)$ compuesto por las bombillas (vértices) y los cables (aristas). Para hacer las luces más deslumbrantes,

Figura 2: ejemplo con $k=3$ y $n=4$.

el diseñador Ray ideó una forma de especificar el color de las bombillas (vértices) de $G$. Ray quiere asignarles colores que cumplan la siguiente condición. Una coloración de $G$ es propia si se asignan colores a sus vértices de modo que los vértices adyacentes $u$ y $v$ tengan colores diferentes. Las bombillas de $G=(V,E)$ son distinguibles: se nombran con etiquetas $v_1,v_2,\ldots,v_m$. Así, una coloración propia que usa como máximo $\lambda$ colores es una función $f$ con dominio $V$ y codominio $\{1,2,3,\ldots,\lambda\}$, donde $f(u)\ne f(v)$ para vértices adyacentes $u,v\in V$. Las coloraciones propias difieren del mismo modo que estas funciones. El máximo número de formas diferentes de colorear $G$ usando $\lambda$ colores se llama número crítico de $G$.

Dados (1) $n$ (para $L_n$), (2) $k$ (para el polígono regular de $k$ lados) y (3) el número de colores disponibles $\lambda$, debes calcular el número crítico de $G$. Si el resultado es mayor o igual que $10^9+7$, escribe el valor módulo $10^9+7$, es decir, el resto obtenido al dividir el valor real entre $10^9+7$.

Figura 3: ejemplo con $k=4$ y $n=3$.

Entrada

La primera línea del archivo de entrada contiene un entero $L$ ($L\le20$), el número de casos de prueba. Para cada caso, la primera línea contiene tres enteros separados por espacios en blanco que representan $n$, $k$ y $\lambda$.

Restricciones

• $1\le n\le1000000000$.

• $3\le k\le1000000000$ para cada caso de prueba.

• $0\le\lambda\le1000000000$.

Salida

La salida contiene una línea por caso de prueba. Cada línea contiene un entero no negativo que representa el número crítico de $G$. Si el resultado es mayor o igual que $10^9+7$, escribe el valor módulo $10^9+7$, es decir, el resto obtenido al dividir el valor real entre $10^9+7$.

Ejemplos

Entrada 1

1
2 3 3

Salida 1

162