Сума і XOR

У звичайний весняний день перед Даніяром знову постає цікаве завдання:

Знайдіть усі можливі масиви довжини n, де кожен елемент 1 ≤ a[i] < 2^{\text{number\_of\_bits}}, 0 ≤ i < 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 (1 ≤ n ≤ 5000),

• sum (1 ≤ sum ≤ 3000),

• number of bits (1 ≤ number of bits ≤ 30),

• xor_sum (1 ≤ xor_sum < 2^{\text{number\_of\_bits}}).

Вихідні дані

Виведіть відповідь за модулем 10^9 + 9.

Приклад

У першому прикладі можливі два масиви: {5, 7}, {7, 5}.

Приклади