「GMOI R2-T4」电子木鱼

给你 $n$，表示一共有 $n$ 位赛博佛祖，编号依次为 $1 \sim n$。 第 $i\ (1 \leq i \leq n)$ 位赛博佛祖可以对应为一个二元组 $\langle S_i, d_i \rangle$，其中 $S$ 在任意时刻均为 $\{1, 2, 3, \dots, m\}$ 的一个子集（可以为空），而 $d_i$ 为 $1 \sim m$ 间的整数。 如果在某一时刻，存在一位赛博佛祖的 $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$ 为你加功德。 现在作为电子资本家的你，想要功德无量。你想知道，最少再请来几位赛博佛祖，可以使得你的这些佛祖们 **源源不断地** 为你加功德。假设这个答案是 $s$（可以为 $0$），那么新的佛祖们的编号依次为 $(n+1) \sim (n+s)$。 **因为你是个资本家，有时候你不想请那么多佛祖**。所以你有许多组询问，对于一组 $l, r$，设 $f(l, r)$ 表示如果初始只有 $[l, r]$ 之间的佛祖，答案将会是多少，注意，每组询问相互独立，上一次添加的佛祖不会延续到以后的询问中。 为了避免太多的输出，你只需要输出： $$\sum\limits_{l=1}^n\sum\limits_{r=l}^n f(l,r)\times2^l$$ 即可，答案对 $10^9 + 7$ 取模。 ## Input 第一行，两个整数 $n, m$。 接下来 $n$ 行，第 $i$ 行首先一个整数描述 $d_i$，接着一个长度为 $m$ 的 $\texttt{01}$ 字符串表示 $S_i$。如果第 $j$ 个字符为 $1$，表示 $j \in S_i$；否则 $j \notin S_i$。 ## Output 一行，表示最终答案取模后的值。 [samples] ## Background 运营电子资本，招聘赛博佛祖，积累虚拟功德。 功德无量，随喜赞叹。 111 ## Note ### 数据规模与约定 **本题采用捆绑测试。** - Subtask 0（10 pts）：$n \leq 10$，$m \leq 5$。 - Subtask 1（10 pts）：$n \leq 300$，$m \leq 10$。 - Subtask 2（15 pts）：$n \leq 1024$，$m \leq 10$。保证每个 $S_i$ 均不同。 - Subtask 3（15 pts）：$n \leq 10^4$。 - Subtask 4（10 pts）：每个 $S_i$ 均在 $2^m$ 种情况中等概率随机生成，$d_i$ 均在 $m$ 种情况中等概率随机生成。 - Subtask 5（40 pts）：无特殊限制。 对于所有数据，保证 $1 \leq n \leq 10^5$，$1 \leq m \leq 17$。