给定一个整数 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}。