New Year and Entity Enumeration
Contest: Good Bye 2017
Difficulty rating: 2500
Tags: bitmasks, combinatorics, dp, math

You are given an integer m.

Let M = 2m - 1.

You are also given a set of n integers denoted as the set T. The integers will be provided in base 2 as n binary strings of length m.

A set of integers S is called "good" if the following hold.

1. If $$a \in S$$, then $$a \text{ XOR } M \in S$$.
2. If $$a,b\in S$$, then $$a \text{ AND } b \in S$$
3. $$T \subseteq S$$
4. All elements of S are less than or equal to M.

Here, $$\text{XOR}$$ and $$AND$$ refer to the bitwise XOR and bitwise AND operators, respectively.

Count the number of good sets S, modulo 109 + 7.

Input format:
The first line will contain two integers m and n (1 ≤ m ≤ 1 000, 1 ≤ n ≤ min(2m, 50)).

The next n lines will contain the elements of T. Each line will contain exactly m zeros and ones. Elements of T will be distinct.

Output format:
Print a single integer, the number of good sets modulo 109 + 7.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
An example of a valid set S is {00000, 00101, 00010, 00111, 11000, 11010, 11101, 11111}.

Example input:
5 3
11010
00101
11000

Example output:
4

Example input:
30 2
010101010101010010101010101010
110110110110110011011011011011

Example output:
860616440

Editorial:
Let's ignore T for now, and try to characterize good sets S.
For every bit position i, consider the bitwise AND of all elements of S which have the i-th bit on (note, there is at least one element in S which has the i-th bit on, since we can always $$\text{XOR}$$ by m). We can see that this is equivalent to the smallest element of S that contains the i-th bit. Denote the resulting number as f(i).
We can notice that this forms a partition of the bit positions, based on the final element that we get. In particular, there can't be a scenario where there is two positions x, y with $$f(x) \neq f(y)$$ such that $$f(x) \text{ AND } f(y) \neq 0$$. To show this, let $$b = f(x) \text{ AND } f(y)$$, and without loss of generality, let's assume $$b \neq f(x)$$ (it can't be simultaneously equal to f(x), f(y) since $$f(x) \neq f(y)$$). If the x-th bit in b is on, we get a contradiction, since b is a smaller element than f(x) that contains the x-th bit. If the x-th bit in b is off, then, $$f(x) \text{ AND } (b \text{ XOR } M)$$ is a smaller element of S that contains the x-th bit.
So, we can guess at this point that good sets S must be partitions of {1, 2, ..., m}.
Given a partition, we can construct a valid good set as follows. We can observe that a good set S must be closed under bitwise OR also. To prove this, for any two elements $$a,b\in S$$, $$a \text{ OR } b = ((a \text{ XOR } M) \text{ AND } (b \text{ XOR } M)) \text{ XOR } M$$. Since the latter is some composition of XORs and ANDs, it it also in S. So, given a partition, we can take all unions of some subset of the partitions to get S.
For an actual solution, partitions can be computed with bell numbers, which is an O(m2) dp (see this: http://mathworld.wolfram.com/BellNumber.html).
Now, back to T, we can see that this decides some partitions beforehand. In particular, for each bit position, we can make a n-bit mask denoting what its value is in each of the n given values. The partitions are based on what these masks are. We can find what the sizes of these splits are, then multiply the ways to partition each individual split together to get the answer.