Задачи
Вложенные множества
Вложенные множества
\includegraphics{https://static.e-olymp.com/content/f0/f0d910cff567ab09af3734060fb5187742a27177.jpg}
\includegraphics{https://static.e-olymp.com/content/f0/f0d910cff567ab09af3734060fb5187742a27177.jpg}
\includegraphics{https://static.e-olymp.com/content/f0/f0d910cff567ab09af3734060fb5187742a27177.jpg}
\includegraphics{https://static.e-olymp.com/content/f0/f0d910cff567ab09af3734060fb5187742a27177.jpg}
Петя недавно узнал о понятии множества и вложенности множеств. Он заинтересовался последовательностями \textbf{S_0} \textbf{S_1} \textbf{S_2} … \textbf{S_n}, у которых каждый следующий элемент --- подмножество предыдущего, \textbf{S_0} --- некоторое конечное множество \textbf{\{a_1, a_2, …, a_m\}}.
\includegraphics{https://static.e-olymp.com/content/2d/2d171744a01cb36b4ae64db9a50f6d7e309a4ee3.jpg}
Петя отметил: каждому из вложенных множеств можно поставить в соответствие целое число \textbf{H(S) =} \textbf{2^\{k-1\}}. Таким образом \textbf{H(S_0) = 2^m -- 1}, \textbf{H(Ø) = 0}.
Петя произвольным образом выбрал \textbf{n} чисел: \textbf{h_1}, \textbf{h_2}, …, \textbf{h_n}. Ему стало интересно: сколько существует разных наборов вложенных множеств \textbf{S_1}, \textbf{S_2}, …, \textbf{S}_\{n \} при \textbf{H}(\textbf{S_1}) = \textbf{h_\{1 \}(mod 41)}, \textbf{H}(\textbf{S_2}) = \textbf{h_\{2 \}(mod 41)}, …, \textbf{H}(\textbf{S_n}) = \textbf{h_\{n \}(mod 41)}? К сожалению, Петя сбился со счета, поэтому просит Вас о помощи.
\textbf{Входной файл}
Первая строка содержит два целых числа \textbf{n }и \textbf{m }(\textbf{1 }≤ \textbf{n }≤ \textbf{5}, \textbf{1 }≤ \textbf{m }≤ \textbf{20}). Вторая строка содержит \textbf{n }целых чисел \textbf{h_1}, \textbf{h_2}, …, \textbf{h_n}, каждое из которых удовлетворяет условию: \textbf{0 }≤ \textbf{h_k} ≤ \textbf{40}.
\textbf{Выходной файл}
Вывести искомое количество вложенных множеств. Известно, что это число не превосходит \textbf{10^18}.
\textit{\textbf{Пояснение к тестам 1--3}}:
\begin{enumerate}
\item Существует только один вариант: 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.
\item Такой комбинации вложенных множеств не существует.
\item 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.
\end{enumerate}
Входные данные #1
3 5 7 3 3
Выходные данные #1
1
Входные данные #2
3 5 7 4 5
Выходные данные #2
0
Входные данные #3
1 7 3
Выходные данные #3
4
Входные данные #4
3 10 31 29 17
Выходные данные #4
28