P11567 建造军营 II

A 国又在与 B 国激烈交战中。

在前线，A 国有 $n$ 个重要据点。有一些据点间存在双向道路，**每条道路均可以选择是否派遣军队驻守**。 A 国情报部门得知，B 国即将实行 $k$ 个作战计划中的一个。第 $i$ 个作战计划的内容是，向 $p_i$ 据点至 $q_i$ 据点的交通线发动袭击。具体来说，B 国将选择一条**可经过重复据点，但不经过重复道路**的由 $p_i$ 到 $q_i$ 的路径，若这条路径上**存在道路无驻守军队**，则袭击成功。 A 国希望 B 国的任何作战计划都不可能获得成功。除了确保兵力足够以外，A 国**还可以选择一些道路进行焦土行动**——这将防止 B 国通过这条道路实施作战。但是焦土行动本身也会影响 A 国的补给运输，因此**被焦土的道路上不应该部署部队**；同时， A 国要求**在焦土行动后，任意两个据点之间仍然存在至少一条不经过被焦土的道路的路径**。 作为 A 国军队最高参谋部的成员，你被要求给出不同防守计划的方案数——**两个防守计划不同，当且仅当存在一条道路的驻守情况不同，或一条道路焦土行动实施与否的状态不同**。方案数对 $10^9+7$ 取模。

第一行两个整数 $n,k$。 接下来 $n$ 行长度为 $n$ 的 `01` 表格 $w_{1\sim n,1\sim n}$，$w_{i,j}$ 为 `1` 则代表据点 $i$ 与据点 $j$ 间存在道路。 接下来 $k$ 行，每行读入两个整数 $p_i,q_i$。

一行一个整数，表示答案。

对于 $100 \%$ 的数据：$2 \leq n \leq 16$，$0\le k \leq 3n$，$1 \leq p_i,q_i \leq n$，$w_{i,j} = w_{j,i}$，$w_{i,i}=0$。 ::cute-table | 子任务编号 | $n \leq$ | $k \leq$ | 特殊性质 | 分值 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ |$ 3$ | $3n$ | / | $5$ | | $2$ | $6 $| ^ | ^ | $10$ | | $3$ | $16$ | $0$ | ^ | $10$ | | $4$ | ^ | $3n$ | A | $10$ | | $5$ | ^ | ^ | B | $20$ | | $6$ | $10$ | ^ | / | $10$ | | $7$ | $13 $| ^ | ^ | $10$ | | $8$ | $16$ | ^ | ^ | $25$ | 特殊性质 A：保证 $\sum_{i,j} w_{i,j} = 2n-2$。 特殊性质 B：保证 $p_i = 1$。