How to Choose a Subset

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Given a set S of first N nonnegative integers i.e. S = {0, 1, 2, ..., N}. Find number of ways of choosing a K size subset of S with the property that the XORsum of all chosen integers has exactly B set bits in its binary representation (i.e. the bits that are equal to 1). Since the answer can be large, output it modulo (10^{9} + 7). Please refer to notes section for formal definition of XORsum.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The only line of each test case contains three spaceseparated integers N, K and B.
Output
For each test case, output a single line containing the answer to the corresponding test case.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ 10^{9}
 1 ≤ K ≤ 7
 0 ≤ B ≤ 30
Example
Input: 3 2 2 0 2 2 1 2 2 2 Output: 0 2 1
Notes
XORsum of n integers A[1], , , A[n] will be A[1] xor A[2] xor .. A[n]. By xor, we mean bitwise xor.
Explanation
Example case 1. There is no way to choose a subset of 2 integers from {0, 1, 2} such that the XORsum contains 0 set bits.
Example case 2. The two possible subsets in this case are {0, 1} and {0, 2}. In both cases the XORsum (1 and 2 respectively) contains exactly one set bit.
Example case 3. The only possible subset is {1, 2}.
Author:  witua 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/KINT 
Tags  cook56, dynamicprogramming, medium, witua 
Date Added:  3032015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions