Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_10_08 - Znowu te Hanoi

tower of hanoiMał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<=104. 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.


Dodane przez:Adam Bąk
Data dodania:2013-09-11
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.