Сумма и 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] 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^(number of bits)).

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

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

Пример

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

Примеры