题目背景

运营电子资本，招聘赛博佛祖，积累虚拟功德。

功德无量，随喜赞叹。

【Upd 2023/04/05 22:27】增加了两组来自 @嘉然今天吃什么 的 hack 数据。

题目描述

给你 $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$ 取模。

输入格式

第一行，两个整数 $n, m$。

接下来 $n$ 行，第 $i$ 行首先一个整数描述 $d_i$，接着一个长度为 $m$ 的 $\texttt{01}$ 字符串表示 $S_i$。如果第 $j$ 个字符为 $1$，表示 $j \in S_i$；否则 $j \notin S_i$。

输出格式

一行，表示最终答案取模后的值。

4 3
1 010
2 001
3 000
3 001

52

5 4
1 1000
4 0100
1 0000
2 0001
2 0000

128

提示

数据规模与约定

本题采用捆绑测试。

• 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$。