And Tuples

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
A pair of nonnegative integers (A,B) is called andpair if A & B = B, i.e., bitwiseand of A and B is equal to B. Similarly, a tuple of K nonnegative integers (A_{1},A_{2},A_{3} .. A_{K}) is called andtuple if A_{i} & A_{i+1} = A_{i+1} for 1≤i≤K1.
Given two integers N and K, how many andtuples of size K exist such that the sum of the elements of the tuple is N?
Input
First line contains T, the number of testcases, then T lines follow. Each of the following lines contain two spaceseparated integers K and N.
Output
For each testcase, print a single line containing the answer. Since the number can be quite large, print the answer modulo 1000000009.
Constraints
Example
Input:
2
3 2
4 2
Output:
2
2
Explanation:
 In the first case, the two andtuples are (2,0,0) and (1,1,0).
 In the second case they are (2,0,0,0) and (1,1,0,0).
Author:  piyushkumar 
Tester:  xiaodao 
Editorial  http://discuss.codechef.com/problems/ANDTUPLE 
Tags  bit, dynamicprogramming, easymedium, ltime17, memoization, piyushkumar, recursion 
Date Added:  1102014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
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. 