Chang and Beautiful Sequences

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
The beauty of any sequence of integers in the BitLand is defined as the product of the number of integers in the list and the Bitwise XOR of those integers. Our little Chef Chang liked this way of defining the beauty of a sequence and henceforth, came up with the following puzzle.
Find out how many sequences of nonnegative integers of length N exist such that the sum of beauty values of all their subsequences modulo 10^{9} + 7 equals a given integer B. Each element in the sequence should be strictly less than a given integer C (fixed to 2^{20}).
Since, the number of such sequences can be large, output this number modulo 10^{9} + 7.
Help the people of BitLand to solve this puzzle.
Input
The first line of the input contains an integer T denoting number of test cases.
First line of each test case contains three space separated N, B and C as mentioned in the statement.
Output
For each test case, output an integer corresponding to the answer to the test case in a separate line.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 10^{6}
 1 ≤ B ≤ 10^{9} + 6
 C = 2^{20}
Example
Input: 3 2 0 1 2 3 2 2 2922 1024 Output: 1 2 616
Explanation
Example 1. Only possible sequence will be 0 0. Its beauty value will be zero.
Example 2.The subsequences with beauty equal to 3 will be 0 1 and 1 0. So, the answer is 2.
Example 3. There are 616 sequences in total that have length 2 and each integer is less than 1024 such that sum of the beauty values of their subsequences modulo 10^{9} + 7 is 2922.
Note
Please note that the above three examples don't have C = 2^{20}. These examples are just for making sure that you understand the problem correctly. In the test data it will be guaranteed that C is indeed 2^{20}.
Example
Input:1 2 345 1048576 Output: 100
Explanation
There are 100 sequences in total that have length 2 and each integer is less than 1048576 such that sum of the beauty values of their subsequences modulo 10^{9} + 7 is 345.
Author:  prateekg603 
Editorial  https://discuss.codechef.com/problems/CHNGSEQ 
Tags  bit, combinatorics, cook84, hard, math, prateekg603 
Date Added:  25062017 
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