P16535 [THUPC 2026 Final] Power Supply Network

From the final of the 2026 Tsinghua University Student Programming Contest and Intercollegiate Invitational (THUPC2026). Resources such as the editorial can be found at https://github.com/dapingguo8/THUPC2026-final. > After finishing the yearbook, the venue was preparing to start the nighttime lighting effects. However, since the backstage power supply network had not been configured yet, the long-awaited holographic projector still could not be turned on. > > The entire power grid consists of many relay nodes, and these nodes must be connected to two parallel main power modules. According to the electrical safety protocol, adjacent nodes within the same module are very likely to cause phase resonance. Therefore, the system has a strict parity restriction on the number of neighbors that each node has within its own module. > > Facing the complicated transmission lines, Xiao S pulled out a stack of old test records. Xiao T pointed out that, since the tests back then were carried out level by level along the hierarchy of the grid, the node sets involved in the records have a regular nested structure: for any two records, the node sets they involve are either completely disjoint, or one strictly contains the other. > > Blind trial and error is not only time-consuming but also highly risky. In order to configure the power supply network as soon as possible, Xiao T and Xiao S need to restore in advance, for each test, the number of ways to connect all nodes to the main modules.

The power supply network contains $n$ nodes. Nodes are connected by several bidirectional transmission lines, forming an undirected graph. When configuring the network, all nodes will be assigned to two independent main power modules. For node $i \ (1 \le i \le n)$, define its **same-module neighbor count** $d_i$ as: within the power module that node $i$ is connected to, the number of nodes that have a direct line connected to node $i$. Xiao S found records of $q$ tests. Each test record is represented by a string $s$ of length $n$. For node $i \ (1 \le i \le n)$: - If $s_i = \text{`0'}$, then in this configuration, node $i$ must have an even same-module neighbor count $d_i$; - If $s_i = \text{`1'}$, then in this configuration, node $i$ must have an odd same-module neighbor count $d_i$; - If $s_i = \text{`?'}$, then node $i$ is not involved in the record, i.e. there is no requirement on the parity of $d_i$. Xiao T pointed out that the node sets involved in the records have a regular nested structure. Specifically, let the node set involved in the $i$-th test $(1 \le i \le q)$ be $S_i$ (i.e. the set of positions in the string that are not `?`). Then for any two different test records $i, j \ (1 \le i < j \le q)$, $S_i$ and $S_j$ must satisfy exactly one of the following three relations: $S_i \subseteq S_j$, $S_j \subseteq S_i$, or $S_i \cap S_j = \varnothing$. To configure the power supply network as soon as possible, you need to help Xiao T and Xiao S compute, for each test, the number of essentially different ways to connect all nodes to the two main modules. Two assignments are considered different if and only if there exists at least one node that is connected to different main modules in the two assignments. Since the answer may be large, you only need to output it modulo $10 ^ 9 + 7$.

The first line contains two positive integers $n, q \ (1 \le n, q \le 3 \times 10 ^ 3)$. The next $n$ lines each contain a $01$ string of length $n$. The $j \ (1 \le j \le n)$-th character of the $i \ (1 \le i \le n)$-th line indicates whether there is a transmission line between node $i$ and node $j$: `1` if there is, otherwise `0`. The next $q$ lines each contain a string $s$ of length $n$, representing one test record.

Output $q$ lines. Each line contains a non-negative integer, representing the number of essentially different ways to connect all nodes to the two main modules in that test, modulo $10 ^ 9 + 7$.

For the first test in Sample 1, there are four possible connection assignments: 1. Connect all nodes to the first main module. 2. Connect all nodes to the second main module. 3. Connect nodes $1, 2$ to the first main module, and connect node $3$ to the second main module. 4. Connect nodes $1, 2$ to the second main module, and connect node $3$ to the first main module. Translated by ChatGPT 5