AlgoLiga 2018

Mały Jasio bawi się w zmodyfikowaną wersję wieży Hanoi. Posiada on k, ponumerowanych kolejnymi liczbami naturalnymi, słupków oraz n krążków o różnych średnicach. Jako, że nie bardzo umie rozwiązać ten klasyczny problem, to postanowił że do obiadu ułoży wszystkie możliwe konfiguracje (a więc nawet te nielegalne w problemie wieży Hanoi) krążków na zestawie słupków. Dwie konfiguracje uważamy za różne jeśli któreś dwa, odpowiadające sobie, słupki z tych konfiguracji zawierają różną liczbę krążków lub inną ich kolejność. Nasuwa się więc pytanie - czy Jasio zdąży na obiad?

Wejście

Wejście rozpoczyna liczba testów 0<t<=10⁴. Następnie każdy test w oddzielnej linii. Pojedynczy test składa się z dwóch liczb, kolejno: 0<=n<=2000, 0<=k<=2000.

Wyjście

Dla każdego testu należy w oddzielnej linii wypisać liczbę wszystkich możliwych konfiguracji n krążków na k słupkach modulo 1009.

Przykład

Wejście:
2
2 2
3 2

Wyjście:
6
24

Wyjaśnienie do przykładu

W pierwszym teście mamy dwa krążki o średnicach 1 i 2 kolejno oraz słupki o numerach 1 i 2 kolejno. Wszystkich możliwych konfiguracji jest 6 i są to:

<<1,2>, <>>; <<2,1>, <>>; <<>, <1,2>>; <<>, <2,1>>; <<1>, <2>>; <<2>, <1>>

Wyjaśnienie notacji: na i-tej pozycji ciągu jest ciąg kolejnych krążków (kolejność od wierzchołka stosu) znajdujących się na i-tym słupku.

Dla n=3 oraz k=2 tych konfiguracji jest 24.