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 ≤ a[i]
< 2^(number_of_bits)
, 0 ≤ i < n with the following conditions:
Sum of the array is equal to sum, i.e. a[0]
+ a[1]
+ ... + a[n - 1]
= sum.
XOR sum of the array is equal to xor_sum, i.e. a[0]
xor a[1]
xor ... xor a[n - 1]
= xor_sum.
To simplify, you are asked to find the answer modulo 10^9
+ 9.
A single line contains 4 integers:
n (1 ≤ n ≤ 5000),
sum (1 ≤ sum ≤ 3000),
number_of_bits (1 ≤ number_of_bits ≤ 30),
xor_sum (1 ≤ xor_sum < 2^(number_of_bits)
).
Output the answer to the problem modulo 10^9
+ 9.
In the first sample test, there are two possible arrays: {5, 7}, {7, 5}.