New Year and Entity Enumeration

题意翻译

题目描述： 给你一个整数 m ，设 $M = 2^m - 1$ 。 给你一个包含 $n$ 个整数的集合，记作 $T$ 。其元素会以 $m$ 位二进制串的形式输入。 称一个整数集合是“好”的，当且仅当以下条件同时满足： - 如果 $a \in S$ , 则 $a \text{ XOR } M \in S$ - 如果 $a, b \in S$ , 则 $a \text{ AND } b \in S$ - $T \subseteq S$ - $S$ 的所有元素都不超过 $M$ 在这里，$\text{XOR}$ 和 $\text{AND}$ 分别指按位异或、按位与运算。 求“好”的集合的个数模 $10^9 + 7$ 的结果。 输入格式： 第一行包含两个整数 $m$ 和 $n(1 \le m \le 1000, 1 \le n \le \min(2^m, 50))$ 。 接下来 $n$ 行，表示集合 $T$ 的所有元素。每行恰有 $m$ 个字符，且都为 `0` 或 `1` 。保证输入的元素两两不同。 输出格式： 输出一个整数，表示“好”的集合的个数模 $10^9 + 7$ 的结果。 样例说明： 一个合法的集合 SS 的例子是 $\{ 00000, 00101, 00010, 00111, 11000, 11010, 11101, 11111 \}$ 。 感谢@hanako 提供的翻译

题目描述

You are given an integer $ m $ . Let $ M=2^{m}-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 , then . 2. If , then  3.  4. All elements of $ S $ are less than or equal to $ M $ . Here,  and  refer to the bitwise XOR and bitwise AND operators, respectively. Count the number of good sets $ S $ , modulo $ 10^{9}+7 $ .

输入输出格式

输入格式

The first line will contain two integers $ m $ and $ n $ ( $ 1<=m<=1000 $ , $ 1<=n<=min(2^{m},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.

输出格式

Print a single integer, the number of good sets modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

5 3
11010
00101
11000

输出样例 #1

4

输入样例 #2

30 2
010101010101010010101010101010
110110110110110011011011011011

输出样例 #2

860616440

说明

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