English · Original
Chinese · Translation
Formal · Original
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
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 109 + 7.
## Input
The first line will contain two integers _m_ and _n_ (1 ≤ _m_ ≤ 1 000, 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.
## Output
Print a single integer, the number of good sets modulo 109 + 7.
[samples]
## Note
An example of a valid set _S_ is {00000, 00101, 00010, 00111, 11000, 11010, 11101, 11111}.
给定一个整数 $m$。
令 $M = 2^m - 1$。
你还被给定一个包含 $n$ 个整数的集合，记为集合 $T$。这些整数将以二进制形式给出，即 $n$ 个长度为 $m$ 的二进制字符串。
一个整数集合 $S$ 被称为“好”的，当且仅当满足以下条件：
这里，$\oplus$ 和 $\&$ 分别表示按位异或和按位与运算符。
请计算“好”集合 $S$ 的数量，对 $10^9 + 7$ 取模。
第一行包含两个整数 $m$ 和 $n$（$1 ≤ m ≤ 1 000$，$1 ≤ n ≤ \min(2^m, 50)$）。
接下来的 $n$ 行包含集合 $T$ 的元素。每行恰好包含 $m$ 个 0 和 1。集合 $T$ 中的元素互不相同。
请输出一个整数，表示“好”集合的数量，对 $10^9 + 7$ 取模。
一个有效的集合 $S$ 的例子是 {00000, 00101, 00010, 00111, 11000, 11010, 11101, 11111}。
## Input
第一行包含两个整数 $m$ 和 $n$（$1 ≤ m ≤ 1 000$，$1 ≤ n ≤ \min(2^m, 50)$）。接下来的 $n$ 行包含集合 $T$ 的元素。每行恰好包含 $m$ 个 0 和 1。集合 $T$ 中的元素互不相同。
## Output
请输出一个整数，表示“好”集合的数量，对 $10^9 + 7$ 取模。
[samples]
## Note
一个有效的集合 $S$ 的例子是 {00000, 00101, 00010, 00111, 11000, 11010, 11101, 11111}。
**Definitions**
Let $ m, n \in \mathbb{Z}^+ $ with $ 1 \leq m \leq 1000 $, $ 1 \leq n \leq \min(2^m, 50) $.
Let $ M = 2^m - 1 $.
Let $ T \subseteq \{0,1\}^m $ be a set of $ n $ distinct binary strings of length $ m $, interpreted as integers in $ [0, M] $.
Let $ \mathcal{S} \subseteq \{0,1\}^m $ be a subset of integers (bitstrings) of length $ m $.
**Constraints**
- $ T \subseteq \{0,1\}^m $, $ |T| = n $, all elements distinct.
- $ \mathcal{S} $ must satisfy: for all $ x, y \in \mathcal{S} $,
$$
x \oplus y \in \mathcal{S} \quad \text{and} \quad x \land y \in \mathcal{S}.
$$
- Additionally, $ T \subseteq \mathcal{S} $.
**Objective**
Count the number of subsets $ \mathcal{S} \subseteq \{0,1\}^m $ such that:
1. $ T \subseteq \mathcal{S} $,
2. $ \mathcal{S} $ is closed under bitwise XOR ($ \oplus $) and bitwise AND ($ \land $),
modulo $ 10^9 + 7 $.
API Response (JSON)
{
"problem": {
"name": "E. New Year and Entity Enumeration",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF908E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given an integer _m_.\n\nLet _M_ = 2_m_ - 1.\n\nYou 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_.\n\nA set...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "给定一个整数 $m$。\n\n令 $M = 2^m - 1$。\n\n你还被给定一个包含 $n$ 个整数的集合，记为集合 $T$。这些整数将以二进制形式给出，即 $n$ 个长度为 $m$ 的二进制字符串。\n\n一个整数集合 $S$ 被称为“好”的，当且仅当满足以下条件：\n\n这里，$\\oplus$ 和 $\\&$ 分别表示按位异或和按位与运算符。\n\n请计算“好”集合 $S$ 的数量，对 $10^9 + 7$ 取...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ m, n \\in \\mathbb{Z}^+ $ with $ 1 \\leq m \\leq 1000 $, $ 1 \\leq n \\leq \\min(2^m, 50) $. \nLet $ M = 2^m - 1 $. \nLet $ T \\subseteq \\{0,1\\}^m $ be a set of $ n $ distinct binary s...",
"is_translate": false,
"language": "Formal"
}
]
}