Sum and XOR#10638
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 where each element 1 \le a_i < 2^{\text{number\_of\_bits}}, 0 \le i < n with the following conditions:
- Sum of the array is equal to , i.e. a_0 + a_1 + \ldots + a_{n-1} = \text{sum}. - XOR sum of the array is equal to , i.e. a_0 \oplus a_1 \oplus \ldots \oplus a_{n-1} = \text{xor\_sum}.
To simplify, you are asked to find the answer modulo 10^9 + 9.
A single line contains integers:
- (1 \le n \le 5000), - (1 \le \text{sum} \le 3000), - (1 \le \text{number\_of\_bits} \le 30), - (1 \le \text{xor\_sum} < 2^{\text{number\_of\_bits}}).
Output the answer to the problem modulo 10^9 + 9.
Example 1
Example 2
Example 3
Example 4
In the first sample test, there are two possible arrays: , .