Вкладені множини#7033
Петрик нещодавно дізнався про поняття множини і вкладення множин. Він зацікавився послідовностями S_0 \supset S_1 \supset S_2 \supset \ldots \supset S_n, у яких кожний наступний елемент — підмножина попереднього, а S_0 — певна скінченна множина \{a_1, a_2, \ldots, a_m\}.
Петрик зауважив: кожній з вкладених множин можна поставити у відповідність ціле число H(S) = \sum_{a_k \in S} 2^{k-1}. Таким чином H(S_0) = 2^m - 1, H(\emptyset) = 0.
Петрик випадковим чином обрав чисел: h_1, h_2, , h_n. Йому стало цікаво: скільки існує різних наборів вкладених множин S_1, S_2, , S_n при H(S_1) \equiv h_1 \pmod{41}, H(S_2) \equiv h_2 \pmod{41}, , H(S_n) \equiv h_n \pmod{41}? На жаль, Петрик збився з рахунку, тому просить вас про допомогу.
Перший рядок містить два цілих числа та (1 \leq n \leq 5, 1 \leq m \leq 20).
Другий рядок містить цілих чисел h_1, h_2, , h_n, кожне з яких задовольняє умову: 0 \leq h_k \leq 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, H(\{a_1, a_3, a_5, a_7\}) = 2^0 + 2^2 + 2^4 + 2^6 = 1 + 4 + 16 + 64 = 85 = 2 \cdot 41 + 3, H(\{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 \cdot 41 + 3.
Приклад 1
Приклад 2
Приклад 3
Приклад 4