← 返回题目列表

Codeforces · 908/E

E. 新年和实体枚举

中文机器翻译题面 查看原题

给定一个整数 m。

设 M = 2m - 1。

还给您一组 n 个整数,表示为集合 T。这些整数将以 2 为基数作为 n 个长度为 m 的二进制字符串提供。

如果以下条件成立,则一组整数 S 被称为“好”。

1. 如果 $$a \in S$$,则 $$a \text{ XOR } M \in S$$。
2. 如果 $$a,b\in S$$,则 $$a \text{ AND } b \in S$$
3. $$T \subseteq S$$
4. S 的所有元素都小于或等于 M。

这里,$$\text{XOR}$$ 和 $$AND$$ 分别指按位异或和按位与运算符。

计算好组 S 的数量,以 109 + 7 为模。

输入

第一行将包含两个整数 m 和 n (1 ≤ m ≤ 1 000, 1 ≤ n ≤ min(2m, 50))。

接下来的 n 行将包含 T 的元素。每行将恰好包含 m 个零和一。 T 的元素将是不同的。

输出

打印一个整数,好的集合数模 109 + 7。

示例

输入 #1

5 3
11010
00101
11000

输出 #1

4

输入 #2

30 2
010101010101010010101010101010
110110110110110011011011011011

输出 #2

860616440

注意

有效集合S的示例是{00000, 00101, 00010, 00111, 11000, 11010, 11101, 11111}。