题目背景

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

输出格式

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

2 1
01
10
1 2

1

参见下发文件

参见下发文件

提示

对于 $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$。