题目背景

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

功德无量，随喜赞叹。

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

【Upd 2023/04/08 14:02】更改了数据范围表格，并且微调了测试点编号。

题目描述

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

因为你是个资本家，有时候你不想请那么多佛祖。所以你有许多组询问，对于一组 $\bm{l, r}$，设 $\bm{f(l,r)}$ 表示如果初始只有 $\bm{[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 捆绑测试。

编号	$n\le$	$m\le$	特殊性质	测试点	分数
$0$	$10$	$5$	$\bf -$	$1\sim 8$	$10$
$1$	$300$	$10$		$9\sim 13$
$2$	$1024$		$\bf A$	$14\sim 19$	$15$
$3$	$10^4$	$17$	$\bf -$	$20\sim 26$
$4$	$10^5$		$\bf B$	$27\sim 30$	$10$
$5$			$\bf -$	$31\sim 37$	$40$

• 特殊性质 $\bf A$：保证每个 $S_i$ 均不同；
• 特殊性质 $\bf B$：每个 $S_i$ 均在 $2^m$ 种情况中等概率随机生成，$d_i$ 均在 $m$ 种情况中等概率随机生成。

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le m\le 17$。