Вложенные множества
Петя недавно узнал о понятии множества и вложенности множеств. Он заинтересовался последовательностями 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.