{"raw_statement":[{"iden":"background","content":"运营电子资本，招聘赛博佛祖，积累虚拟功德。\n\n功德无量，随喜赞叹。\n\n111"},{"iden":"statement","content":"给你 $n$，表示一共有 $n$ 位赛博佛祖，编号依次为 $1 \\sim n$。\n\n第 $i\\ (1 \\leq i \\leq n)$ 位赛博佛祖可以对应为一个二元组 $\\langle S_i, d_i \\rangle$，其中 $S$ 在任意时刻均为 $\\{1, 2, 3, \\dots, m\\}$ 的一个子集（可以为空），而 $d_i$ 为 $1 \\sim m$ 间的整数。\n\n如果在某一时刻，存在一位赛博佛祖的 $S_i$ 为空集，佛祖会感到很开心而给你加功德。具体地，他会敲响第 $d_i$ 个木鱼，并 **在下一时刻同时** 影响所有的 $n$ 位赛博佛祖（包括他自己）。对第 $j(1 \\leq j \\leq n)$ 位赛博佛祖，如果 $d_i \\in S_j$，那么将从 $S_j$ 内删去 $d_i$；否则向 $S_j$ 内加入 $d_i$。如果有多位赛博佛祖的 $S_i$ 为空集，取编号最小的 $i$ 为你加功德。\n\n现在作为电子资本家的你，想要功德无量。你想知道，最少再请来几位赛博佛祖，可以使得你的这些佛祖们 **源源不断地** 为你加功德。假设这个答案是 $s$（可以为 $0$），那么新的佛祖们的编号依次为 $(n+1) \\sim (n+s)$。\n\n**因为你是个资本家，有时候你不想请那么多佛祖**。所以你有许多组询问，对于一组 $l, r$，设 $f(l, r)$ 表示如果初始只有 $[l, r]$ 之间的佛祖，答案将会是多少，注意，每组询问相互独立，上一次添加的佛祖不会延续到以后的询问中。\n\n为了避免太多的输出，你只需要输出： \n\n$$\\sum\\limits_{l=1}^n\\sum\\limits_{r=l}^n f(l,r)\\times2^l$$\n\n即可，答案对 $10^9 + 7$ 取模。"},{"iden":"input","content":"第一行，两个整数 $n, m$。\n\n接下来 $n$ 行，第 $i$ 行首先一个整数描述 $d_i$，接着一个长度为 $m$ 的 $\\texttt{01}$ 字符串表示 $S_i$。如果第 $j$ 个字符为 $1$，表示 $j \\in S_i$；否则 $j \\notin S_i$。"},{"iden":"output","content":"一行，表示最终答案取模后的值。"},{"iden":"note","content":"### 数据规模与约定\n\n**本题采用捆绑测试。**\n\n- Subtask 0（10 pts）：$n \\leq 10$，$m \\leq 5$。\n- Subtask 1（10 pts）：$n \\leq 300$，$m \\leq 10$。\n- Subtask 2（15 pts）：$n \\leq 1024$，$m \\leq 10$。保证每个 $S_i$ 均不同。\n- Subtask 3（15 pts）：$n \\leq 10^4$。\n- Subtask 4（10 pts）：每个 $S_i$ 均在 $2^m$ 种情况中等概率随机生成，$d_i$ 均在 $m$ 种情况中等概率随机生成。\n- Subtask 5（40 pts）：无特殊限制。\n\n对于所有数据，保证 $1 \\leq n \\leq 10^5$，$1 \\leq m \\leq 17$。"}],"translated_statement":null,"sample_group":[["4 3\n1 010\n2 001\n3 000\n3 001","52"],["5 4\n1 1000\n4 0100\n1 0000\n2 0001\n2 0000","128"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}