Nested Sets#7033
Petryk recently learned about the concept of sets and nested sets. He became interested in sequences S_0 \supset S_1 \supset S_2 \supset \ldots \supset S_n, where each subsequent element is a subset of the previous one, and S_0 is some finite set \{a_1, a_2, \ldots, a_m\}.
Petryk noted that each nested set can be assigned an integer H(S) = \sum_{a_k \in S} 2^{k-1}. Thus H(S_0) = 2^m - 1, H(\emptyset) = 0.
Petryk randomly selected numbers: h_1, h_2, , h_n. He wondered: how many different sets of nested sets S_1, S_2, , S_n exist such that H(S_1) \equiv h_1 \pmod{41}, H(S_2) \equiv h_2 \pmod{41}, , H(S_n) \equiv h_n \pmod{41}? Unfortunately, Petryk lost count, so he asks for your help.
The first line contains two integers and (1 \leq n \leq 5, 1 \leq m \leq 20).
The second line contains integers h_1, h_2, , h_n, each satisfying the condition: 0 \leq h_k \leq 40.
Output the number of nested sets. It is known that this number does not exceed 10^{18}.
Explanation for tests 1–3:
There is only one option: 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.
No such combination of nested sets exists.
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.
Example 1
Example 2
Example 3
Example 4