POLSKI SPOJ

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.