Cəmi və XOR

Adi bir bahar günündə Dənyarın qarşısında maraqlı bir vəzifə durur:

Uzunluğu n olan bütün mümkün massivləri tapın, burada hər bir element 1 ≤ a[i] < 2^(number_of_bits), 0 ≤ i < n aşağıdakı şərtlərlə:

• Massivin elementlərinin cəmi sum-a bərabərdir, yəni a[0] + a[1] + ... + a[n - 1] = sum.

• Massivin XOR cəmi xor_sum-a bərabərdir, yəni a[0] xor a[1] xor ... xor a[n - 1] = xor_sum.

Sadəlik üçün cavabı 10^9 + 9 modulunda tapmağınız təklif olunur.

Giriş məlumatları

Bir sıra, 4 tam ədədi ehtiva edir:

• 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)).

Çıxış məlumatları

Cavabı 10^9 + 9 modulunda çıxarın.

Nümunə

Birinci nümunədə iki massiv mümkündür: {5, 7}, {7, 5}.