Məsələlər
Сумма и XOR
Сумма и XOR
В самый обычный весенний день перед Данияром снова встает интересная задача:
Найдите все возможные массивы длины n, где каждый элемент 1 ≤ ai
< 2number_of_bits
, 0 ≤ i < n со слеующими условиями:
- Сумма элементов массива равна sum, то есть
a0
+a1
+ ... +an-1
= sum. - XOR сумма массива равна xor_sum, то есть
a0
xora1
xor ... xoran-1
= xor_sum.
Для простоты Вам предлагается найти ответ по модулю 109
+ 9.
Входные данные
Одна строка содержащая 4 целых числа:
- n (1 ≤ n ≤ 5000),
- sum (1 ≤ sum ≤ 3000),
- number of bits (1 ≤ number of bits ≤ 30),
- xor_sum (1 ≤ xor_sum <
2number of bits
).
Выходные данные
Выведите ответ по модулю 109
+ 9.
Пример
В первом примере возможны два массива: {5, 7}, {7, 5}.
Giriş verilənləri #1
2 12 3 2
Çıxış verilənləri #1
2
Giriş verilənləri #2
3 12 3 2
Çıxış verilənləri #2
27
Giriş verilənləri #3
4 16 3 2
Çıxış verilənləri #3
144
Giriş verilənləri #4
3 16 3 2
Çıxış verilənləri #4
9