Сума і XOR#10638
У звичайний весняний день перед Даніяром знову постає цікаве завдання:
Знайдіть усі можливі масиви довжини , де кожен елемент 1 \le a_i < 2^{number\_of\_bits}, 0 \le i < n з наступними умовами:
Сума елементів масиву дорівнює , тобто a_0 + a_1 + \ldots + a_{n-1} = sum.
XOR сума масиву дорівнює xor\_sum, тобто a_0 \oplus a_1 \oplus \ldots \oplus a_{n-1} = xor\_sum.
Для простоти вам пропонується знайти відповідь за модулем 10^9 + 9.
Один рядок, що містить цілих числа:
(1 \le n \le 5000),
(1 \le sum \le 3000),
number\_of\_bits (1 \le number\_of\_bits \le 30),
xor\_sum (1 \le xor\_sum < 2^{number\_of\_bits}).
Виведіть відповідь за модулем 10^9 + 9.
Приклад 1
Приклад 2
Приклад 3
Приклад 4
У першому прикладі можливі два масиви: {, }, {, }.