{"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 of integers _S_ is called \"good\" if the following hold.\n\n1.  If , then .\n2.  If , then\n\n4.  All elements of _S_ are less than or equal to _M_.\n\nHere, and refer to the bitwise XOR and bitwise AND operators, respectively.\n\nCount the number of good sets _S_, modulo 109 + 7.\n\n## Input\n\nThe first line will contain two integers _m_ and _n_ (1 ≤ _m_ ≤ 1 000, 1 ≤ _n_ ≤ _min_(2_m_, 50)).\n\nThe next _n_ lines will contain the elements of _T_. Each line will contain exactly _m_ zeros and ones. Elements of _T_ will be distinct.\n\n## Output\n\nPrint a single integer, the number of good sets modulo 109 + 7.\n\n[samples]\n\n## Note\n\nAn example of a valid set _S_ is {00000, 00101, 00010, 00111, 11000, 11010, 11101, 11111}.","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$ 取模。\n\n第一行包含两个整数 $m$ 和 $n$（$1 ≤ m ≤ 1 000$，$1 ≤ n ≤ \\min(2^m, 50)$）。\n\n接下来的 $n$ 行包含集合 $T$ 的元素。每行恰好包含 $m$ 个 0 和 1。集合 $T$ 中的元素互不相同。\n\n请输出一个整数，表示“好”集合的数量，对 $10^9 + 7$ 取模。\n\n一个有效的集合 $S$ 的例子是 {00000, 00101, 00010, 00111, 11000, 11010, 11101, 11111}。\n\n## Input\n\n第一行包含两个整数 $m$ 和 $n$（$1 ≤ m ≤ 1 000$，$1 ≤ n ≤ \\min(2^m, 50)$）。接下来的 $n$ 行包含集合 $T$ 的元素。每行恰好包含 $m$ 个 0 和 1。集合 $T$ 中的元素互不相同。\n\n## Output\n\n请输出一个整数，表示“好”集合的数量，对 $10^9 + 7$ 取模。 \n\n[samples]\n\n## Note\n\n一个有效的集合 $S$ 的例子是 {00000, 00101, 00010, 00111, 11000, 11010, 11101, 11111}。","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 strings of length $ m $, interpreted as integers in $ [0, M] $.  \n\nLet $ \\mathcal{S} \\subseteq \\{0,1\\}^m $ be a subset of integers (bitstrings) of length $ m $.  \n\n**Constraints**  \n- $ T \\subseteq \\{0,1\\}^m $, $ |T| = n $, all elements distinct.  \n- $ \\mathcal{S} $ must satisfy: for all $ x, y \\in \\mathcal{S} $,  \n  $$\n  x \\oplus y \\in \\mathcal{S} \\quad \\text{and} \\quad x \\land y \\in \\mathcal{S}.\n  $$  \n- Additionally, $ T \\subseteq \\mathcal{S} $.  \n\n**Objective**  \nCount the number of subsets $ \\mathcal{S} \\subseteq \\{0,1\\}^m $ such that:  \n1. $ T \\subseteq \\mathcal{S} $,  \n2. $ \\mathcal{S} $ is closed under bitwise XOR ($ \\oplus $) and bitwise AND ($ \\land $),  \nmodulo $ 10^9 + 7 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF908E","tags":["bitmasks","combinatorics","dp","math"],"sample_group":[["5 3\n11010\n00101\n11000","4"],["30 2\n010101010101010010101010101010\n110110110110110011011011011011","860616440"]],"created_at":"2026-03-03 11:00:39"}}