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.|

CWANYLUL - Cwany Lutek 3

Finał !

Tym razem Lutek przygotował dla ciebie arcytrudne zadanie.
Powiedział, że nie przepuści cię do cukrolandii dopóki nie obliczysz mu jego pracy domowej, która była na wczoraj.
Jego praca domowa składa się tylko z dziwnych napisów w takiej oto formie C(n,k) mod 1009, gdzie C(a,b) to dwumian newtona.

Jako, że mu się nudzi, dał ci na to tylko jedną sekundę. DO DZIEŁA !

Input

W pierwszym wierszu iczba t<=1000 oznaczająca liczbę testów.

W następnych t wierszach dwie liczby n,k z zadania Lutka.

0 ≤ n <10^9

0 ≤ k <10^9

Uwaga: należy rozważyć również przypadki w których k > n.

Output

Wynik dla każdego testu w osobnej linii.

Example

Input:
3
3 1
5 2
10 3
Output: 3
10
120
Notka:
7 kwietnia 2012 dodano więcej testów.

Dodane przez:Krzysztof Lewko
Data dodania:2011-11-26
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.