Background

Operate electronic capital, recruit cyber Buddhas, and accumulate virtual merit.

Infinite merit, rejoice and praise.

111

Problem Description

You are given $n$, meaning there are $n$ cyber Buddhas in total, numbered $1 \sim n$.

The $i$-th $(1 \leq i \leq n)$ cyber Buddha can be represented as an ordered pair $\langle S_i, d_i \rangle$, where $S_i$ is always a subset of $\{1, 2, 3, \dots, m\}$ at any moment (it can be empty), and $d_i$ is an integer between $1 \sim m$.

If at some moment, there exists a cyber Buddha whose $S_i$ is the empty set, the Buddha will feel very happy and add merit to you. Specifically, he will strike the $d_i$-th wooden fish, and at the next moment simultaneously affect all $n$ cyber Buddhas (including himself). For the $j$-th $(1 \leq j \leq n)$ cyber Buddha, if $d_i \in S_j$, then delete $d_i$ from $S_j$; otherwise, add $d_i$ into $S_j$. If multiple cyber Buddhas have $S_i$ as the empty set, the one with the smallest index $i$ will add merit to you.

Now, as an electronic capitalist, you want infinite merit. You want to know the minimum number of additional cyber Buddhas you need to hire so that these Buddhas can continuously add merit for you. Suppose this answer is $s$ (it can be $0$), then the new Buddhas are numbered $(n+1) \sim (n+s)$.

Because you are a capitalist, sometimes you do not want to hire that many Buddhas. So you have many queries. For a query $l, r$, let $f(l, r)$ denote the answer if initially there are only Buddhas in $[l, r]$. Note that each query is independent, and the Buddhas added in the previous query will not carry over to later queries.

To avoid too much output, you only need to output:

$$\sum\limits_{l=1}^n\sum\limits_{r=l}^n f(l,r)\times2^l$$

The answer should be taken modulo $10^9 + 7$.

Input Format

The first line contains two integers $n, m$.

The next $n$ lines: on line $i$, first an integer $d_i$, followed by a $\texttt{01}$ string of length $m$ representing $S_i$. If the $j$-th character is $1$, it means $j \in S_i$; otherwise $j \notin S_i$.

Output Format

One line, the final answer modulo.

4 3
1 010
2 001
3 000
3 001

52

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

128

Hint

Constraints

This problem uses bundled testdata.

• 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$. It is guaranteed that all $S_i$ are distinct.
• Subtask 3 (15 pts): $n \leq 10^4$.
• Subtask 4 (10 pts): each $S_i$ is generated uniformly at random among the $2^m$ possibilities, and each $d_i$ is generated uniformly at random among the $m$ possibilities.
• Subtask 5 (40 pts): no special restrictions.

For all data, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq m \leq 17$.

Translated by ChatGPT 5