Binomial Coefficient

All submissions for this problem are available.
This is a very simple problem. Given the value of N and K, you need to tell us the value of the binomial coefficient C(N,K). You may rest assured that K <= N and the maximum value of N is 1,000,000,000,000,000. Since the value may be very large, you need to compute the result modulo 1009.
Input
The first line of the input contains the number of test cases T, at most 1000. Each of the next T lines consists of two space separated integers N and K, where 0 <= K <= N and 1 <= N <= 1,000,000,000,000,000.
Output
For each test case, print on a new line, the value of the binomial coefficient C(N,K) modulo 1009.
Example
Input: 3 3 1 5 2 10 3 Output: 3 10 120
Author:  moneymachine 
Tags  moneymachine 
Date Added:  16012010 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICON, JAVA, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 
I believe this question has a
I believe this question has a wrong test case!
My algorithm is:
I find n!/k! modulo 1009
then i find (nk)! modulo 1009
and because 1009 is a prime , then both of these numbers are coprime to 1009
and we can use multiplicative inverse of (nk)! modulo 1009
I tested my program for all inputs less than 1000 with a brute force algorithm. I'm sure my algorithm is right and my program works well. but it says wrong answer!!
Please at least give me the test i'm wrong with.
Thanks
(nk)! is not coprime to 1009
(nk)! is not coprime to 1009 when nk>=1009, so your algorithm doesn't work.
Thanks
Thanks
Then what's your idea?
Then what's your idea?
I designed the problem. Use
I designed the problem. Use Lucas theorem to solve it.
Sorry for writing in Persian
Sorry for writing in Persian but I want to make Amir Understand:
ببین یه قضیه ای وجود داره به نام قضیه ی لوکاس که می گه اگر
p
یک عدد اول باشه اونوقت می شه با یه سری محاسبات راحت باقی مانده ی یک ترکیب بر
p
رو به دست آورد.
ویکیپدیا بخون!
As I saw Mr. Merriman's
As I saw Mr. Merriman's answer precomputes C(n,k) for n,k<=1009
I just merged the two algorithms mentioned above. I use Lucas' theorem for big ones and for small ones I find multiplicative inverse of [nk]! mod 1009.
My solutions are
My solutions are memoryfriendly :D
Hi guys, This is a problem
Can anyone help me with this