Задачи
Сумма и XOR
Сумма и XOR
В самый обычный весенний день перед Данияром снова встает интересная задача:
Найдите все возможные массивы длины n, где каждый элемент 1 ≤ a[i]
< 2^(number_of_bits)
, 0 ≤ i < n со слеующими условиями:
Сумма элементов массива равна sum, то есть
a[0]
+a[1]
+ ... +a[n - 1]
= sum.XOR сумма массива равна xor_sum, то есть
a[0]
xora[1]
xor ... xora[n - 1]
= xor_sum.
Для простоты Вам предлагается найти ответ по модулю 10^9
+ 9.
Входные данные
Одна строка содержащая 4 целых числа:
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)
).
Выходные данные
Выведите ответ по модулю 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