eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сумма и XOR

Сумма и XOR

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

В самый обычный весенний день перед Данияром снова встает интересная задача:

Найдите все возможные массивы длины n, где каждый элемент 1a[i] < 2^(number_of_bits), 0i < n со слеующими условиями:

  • Сумма элементов массива равна sum, то есть a[0] + a[1] + ... + a[n - 1] = sum.

  • XOR сумма массива равна xor_sum, то есть a[0] xor a[1] xor ... xor a[n - 1] = xor_sum.

Для простоты Вам предлагается найти ответ по модулю 10^9 + 9.

Входные данные

Одна строка содержащая 4 целых числа:

  • n (1n5000),

  • sum (1sum3000),

  • number of bits (1number of bits30),

  • xor_sum (1xor_sum < 2^(number of bits)).

Выходные данные

Выведите ответ по модулю 10^9 + 9.

Пример

В первом примере возможны два массива: {5, 7}, {7, 5}.

Пример

Входные данные #1
2 12 3 2
Выходные данные #1
2
Входные данные #2
3 12 3 2
Выходные данные #2
27
Входные данные #3
4 16 3 2
Выходные данные #3
144
Входные данные #4
3 16 3 2
Выходные данные #4
9
Источник 2021 KBTU Open, Весна Казахстан, Алма-Ата, 30 мая, Задача A