Problems
Sum and XOR
Sum and XOR
On the very usual day of spring, Daniyar is challenged with an interesting problem once again:
You need to find all possible arrays of length n where each element 1 ≤ ai
< 2number_of_bits
, 0 ≤ i < n with the following conditions:
- Sum of the array is equal to sum, i.e.
a0
+a1
+ ... +an-1
= sum. - XOR sum of the array is equal to xor_sum, i.e.
a0
xora1
xor ... xoran-1
= xor_sum.
To simplify, you are asked to find the answer modulo 109
+ 9.
Input
A single line contains 4 integers:
- n (1 ≤ n ≤ 5000),
- sum (1 ≤ sum ≤ 3000),
- numberofbits (1 ≤ numberofbits ≤ 30),
- xor_sum (1 ≤ xor_sum <
2number_of_bits
).
Output
Output the answer to the problem modulo 109
+ 9.
Example
In the first sample test, there are two possible arrays: {5, 7}, {7, 5}.
Input example #1
2 12 3 2
Output example #1
2
Input example #2
3 12 3 2
Output example #2
27
Input example #3
4 16 3 2
Output example #3
144
Input example #4
3 16 3 2
Output example #4
9