Aby przyciągnąć klientów, właściciel sklepu postanowił zamówić specjalny neon do ustawienia przed sklepem. Składa się on z kilku elementów w kształcie drabiny. Każdy z nich można przedstawić jako graf drabinowy $L_n$, będący płaskim grafem nieskierowanym o $2n$ wierzchołkach i $3n-2$ krawędziach. Wierzchołek reprezentuje żarówkę, a krawędź przewód łączący dwie żarówki. Graf drabinowy jest iloczynem kartezjańskim dwóch grafów ścieżkowych, z których jeden ma tylko jedną krawędź: $L_n=P_n\times P_2$, gdzie $P_n$ jest ścieżką o $n$ wierzchołkach. Rysunek 1 pokazuje $L_6$. Główna rama utrzymująca $k$ elementów drabinowych jest foremnym $k$-kątem.

Rysunek 1: $L_6$.

Każdy bok foremnego $k$-kąta łączy się z górną krawędzią $L_n$. Rysunek 2 pokazuje przypadek $k=3$, $n=4$, a rysunek 3 przypadek $k=4$, $n=3$. Dla wygody neon przedstawiamy jako graf $G=(V,E)$ złożony z żarówek (wierzchołków) i przewodów (krawędzi). Aby światła były bardziej olśniewające,

Rysunek 2: przykład dla $k=3$ i $n=4$.

projektant Ray wymyślił sposób określania kolorów żarówek (wierzchołków) w $G$. Chce przydzielić im kolory tak, aby spełniony był następujący warunek. Kolorowanie $G$ jest poprawne, jeśli sąsiednie wierzchołki $u$ i $v$ otrzymują różne kolory. Żarówki w $G=(V,E)$ są rozróżnialne, czyli mają etykiety $v_1,v_2,\ldots,v_m$. Poprawne kolorowanie żarówek $G$ przy użyciu co najwyżej $\lambda$ kolorów jest więc funkcją $f$ o dziedzinie $V$ i przeciwdziedzinie $\{1,2,3,\ldots,\lambda\}$, gdzie $f(u)\ne f(v)$ dla sąsiednich wierzchołków $u,v\in V$. Kolorowania różnią się wtedy tak samo jak te funkcje. Maksymalna liczba różnych sposobów kolorowania $G$ przy użyciu $\lambda$ kolorów jest nazywana liczbą krytyczną $G$.

Mając (1) $n$ (dla $L_n$), (2) $k$ (dla foremnego $k$-kąta) i (3) liczbę dostępnych kolorów $\lambda$, oblicz liczbę krytyczną $G$. Jeśli wynik jest większy lub równy $10^9+7$, wypisz go modulo $10^9+7$, czyli resztę z dzielenia rzeczywistej wartości przez $10^9+7$.

Rysunek 3: przykład dla $k=4$ i $n=3$.

Wejście

Pierwszy wiersz pliku wejściowego zawiera liczbę całkowitą $L$ ($L\le20$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku pierwszy wiersz zawiera trzy liczby całkowite oddzielone białymi znakami, reprezentujące $n$, $k$ i $\lambda$.

Ograniczenia

• $1\le n\le1000000000$.

• $3\le k\le1000000000$ dla każdego przypadku testowego.

• $0\le\lambda\le1000000000$.

Wyjście

Wyjście zawiera jeden wiersz dla każdego przypadku testowego. Każdy wiersz zawiera jedną nieujemną liczbę całkowitą reprezentującą liczbę krytyczną $G$. Jeśli wynik jest większy lub równy $10^9+7$, wypisz go modulo $10^9+7$, czyli resztę z dzielenia rzeczywistej wartości przez $10^9+7$.

Przykład

Wejście 1

1
2 3 3

Wyjście 1

162