eolymp
Competitions

2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30

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 1ai < 2number_of_bits, 0i < 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 xor a1 xor ... xor an-1 = xor_sum.

To simplify, you are asked to find the answer modulo 109 + 9.

Input

A single line contains 4 integers:

  • n (1n5000),
  • sum (1sum3000),
  • numberofbits (1numberofbits30),
  • xor_sum (1xor_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}.

Time limit 1 second
Memory limit 128 MiB
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
Source 2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30, Problem A