Each box can be represented using a bitmask: ~i^\text{th}~ bit will tell us whether ~i^\text{th}~ toy is present in this box. Our problem can now be reformulated: find the number of subsets of boxes such that total bitwise-or has no zeroes in its binary representation.

We could use dynamic programming and find solutions for each ~f(masks\_left, current\_bitwise\_or)~. This solution has a complexity of ~\mathcal O(N \times 2^M)~ and earns ~50\%~ of the points. We won't go into details of this solution, but various implementations can be found among competitors' solutions.

Let's see how to come up with a faster solution. Let ~b[mask]~ be the number of masks from the input that are submasks of ~mask~. Then the number of subsets whose bitwise-or is a submask of ~mask~ is equal to ~c[mask] = 2^{b[mask]}~. Once we have ~c~ calculated, we get the solution in complexity ~\mathcal O(2^M)~ by using the inclusion-exclusion principle.

But how to get sequence ~b~? Let's take some mask ~1mask~ that begins with ~1~. Here ~mask~ denotes the rest of the bitmask. Let's say we already know the number of its submasks that begin with ~1~. Number of submasks that begin with ~0~ is equal to number of submasks of ~0mask~. This suggests a recursive approach: we solve our problem separately for masks beginning with ~0~ and ~1~, and then combine those solutions into the total solution.

Complexity of finding ~b~ is ~T(2^M) = \mathcal O(2^M) + 2T(2^{M-1}) = \mathcal O(M \times 2^M)~.

Total complexity becomes ~\mathcal O(NM + M \times 2^M)~.

It is also possible to avoid using the inclusion-exclusion principle, since we can calculate ~c~ within at the bottom of the same recursion we use for finding ~b~.

~b~ could also be found by brute force in complexity ~\mathcal O(3^M)~, and this approach is worth ~70\%~ of the points.