问题 C: 船舱

大嘤帝国的东格玛水手，染染，成功竞选上了船长！

竞选上船长后，染染便看到了自己的船，一艘 $n$ 个船舱之间两两不通的半成品木制大船！船舱由 $1,2,\cdots ,n$ 编号，编号为 $i$ 的船舱称为 $i$ 号船舱。

船舱之间两两不通是肯定不行的，不如说，染染希望能将所有的船舱连通。具体而言，有些一对船舱之间可以打通，打通之后这对船舱就可以直接连通。此外，一对船舱之间也可以通过若干对直接连通的船舱间接连通。形式化的，对于船舱 $x$ 和船舱 $y$，如果存在 v1,v2,⋯,vkv1,v2,⋯,vk 满足 v1=xv1=x 和 vk=yvk=y，且对于 $i=1,2,\cdots ,k-1$ 有船舱 vivi 和船舱 vi+1vi+1 之间直接连通，则船舱 $x$ 和船舱 $y$ 之间间接连通。只要所有 $n$ 个船舱两两之间直接或间接连通，就满足了染染要求的所有的船舱之间连通。

除此之外，由于船的结构问题，并不是每一对船舱之间都可以打通也就是直接连通。由于船还没有完全建好，就连哪些一对船舱之间可以打通也是不确定的。具体的情况可以通过一个 $n\times n$ 的概率矩阵来表示，概率矩阵的第 $i$ 行第 $j$ 列上的元素即船舱 $i$ 和船舱 $j$ 能打通的概率，保证概率矩阵是对称矩阵且对角线全为 $0$。

由于船的结构原因，概率矩阵中只有三种元素 $0,1,p$，其中 $p$ 是一个还未确定的概率值。注意每对船舱之间是否能够打通的概率是相互独立的。

由于打通两个船舱有各方面的成本，染染当然希望打通的次数尽量少。形式化的，在船建成后，也就是每对船舱之间能否打通都确定后，染染希望打通船舱，使得船舱之间其恰好连接成为树状结构。在此基础上，染染会给出 $q$ 次询问，第 $i$ 次询问给出一个 $p$ 的可能取值 pipi，要求 p=pip=pi 时打通船舱的不同方案的数量的期望。

本题单个测试点内包含多组测试数据。

输入第一行一个正整数 $T(1\le T\le 20)$，表示数据组数。

每组数据第一行两个正整数 $n(1\le n\le 80)$ 和 q (1≤q≤6×105)q (1≤q≤6×105)，分别表示船上的船舱数量和染染的询问数量。

接下来 $n$ 行，第 $i$ 行一个长度为 $n$ 且仅由字符 $\text{0},\text{1},\text{p}$ 组成的字符串 sisi，表示题面中概率矩阵的第 $i$ 行。

保证概率矩阵是对称矩阵且对角线全为 $0$。

接下来 $q$ 行，第 $i$ 行两个非负整数 ai,bi (0≤ai≤bi<109+7,bi≠0)ai,bi (0≤ai≤bi<109+7,bi=0)，表示染染第 $i$ 次询问的 pi=aibipi=biai。

保证单个测试点内每组数据中 $q$ 的和不超过 3×1063×106。

保证单个测试点内只有最多 $5$ 组数据不满足 $n\le 20$。

为了避免浮点误差和输出量过大，输出对每组数据进行压缩。

对于每组数据，假设染染第 $i$ 次询问的答案为 riri，你只需要输出一行一个压缩后的非负整数 $R$：R=(∑i=1qi⋅ri)mod(109+7)R=(i=1∑qi⋅ri)mod(109+7)

对于第 $1$ 次询问，仅存在一种打通方案 $(1,2),(2,3)$，答案为 $1$。

对于第 $2$ 次询问，存在三种打通方案 $(1,2),(2,3),(1,2),(1,3),(1,3),(2,3)$，答案为 $3$。

对于第 $3$ 次询问，分别有 1221 的概率对应前两次询问，答案为 12(1+3)=221(1+3)=2。