Вкладені множини
Петрик нещодавно дізнався про поняття множини і вкладення множин. Він зацікавився послідовностями S_{0 } S_1 S_2 … S_n, у яких кожний наступний елемент — підмножина попереднього, S_0 — певна скінченна множина {a_1, a_2, …, a_m}.
Петрик зауважив: кожній з вкладених множин можна поставити у відповідність ціле число H(S) = 2^{k-1}. Таким чином H(S_0) = 2^m – 1, H(Ø) = 0.
Петрик випадковим чином обрав n чисел: h_1, h_2, …, h_n. Йому стало цікаво: скільки існує різних наборів вкладених множин S_1, S_2, …, S_{n }при H(S_1) = h_{1 }(mod 41), H(S_2) = h_{2 }(mod 41), …, H(S_n) = h_{n }(mod 41)? На жаль, Петрик збився з рахунку, тому просить вас про допомогу.
Вхідний файл
Перший рядок містить два цілих числа n та m (1 ≤ n ≤ 5, 1 ≤ m ≤ 20).
Другий рядок містить n цілих чисел h_1, h_2, …, h_n, кожне з яких задовольняє умову: 0 ≤ h_k ≤ 40.
Вихідний файл
Вивести шукану кількість вкладених множин. Відомо, що вона не перевищує 10^18.
Пояснення до тестів 1–3:
Існує лише один варіант: S_1 = {a_1, a_2, a_3}, S_2 = S_3 = {a_1, a_2}. H(S_1) = 7, H(S_2) = H(S_3) = 3.
Такої комбінації вкладених множин не існує.
H({a_1, a_2}) = 2^{1 – 1 }+ 2^{2 – 1} = 3, H({a_3, a_4, a_6}) = 2^2 + 2^3 + 2^5 = 4 + 8 + 32 = 44 = 41 + 3, Н({a_1, a_3, a_5, a_7}) = 2^{0 }+ 2^{2 }+ 2^{4 }+ 2^6 = 1 + 4 + 16 + 64 = 85 = 2·41 + 3, Н({a_2, a_3, a_4, a_5, a_6, a_7}) = 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 = 2 + 4 + 8 + 16 + 32 + 64 = 126 = 3·41 + 3.