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 non-negative integers of length N exist such that the sum of beauty values of all their subsequences modulo 109 + 7 equals a given integer B. Each element in the sequence should be strictly less than a given integer C (fixed to 220).
Since, the number of such sequences can be large, output this number modulo 109 + 7.
Help the people of BitLand to solve this puzzle.
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.
For each test case, output an integer corresponding to the answer to the test case in a separate line.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 106
- 1 ≤ B ≤ 109 + 6
- C = 220
Input: 3 2 0 1 2 3 2 2 2922 1024 Output: 1 2 616
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 109 + 7 is 2922.
Please note that the above three examples don't have C = 220. 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 220.
1 2 345 1048576 Output: 100
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 109 + 7 is 345.
|Tags||bit, combinatorics, cook84, hard, math, prateekg603|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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|
Fetching successful submissions
If you are still having problems, see a sample solution here.