该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

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

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

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

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

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

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

输入描述

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

• 输入第一行一个正整数 $T$ ($1 \leq T \leq 20$)，表示数据组数。
• 每组数据第一行两个正整数 $n$ ($1 \leq n \leq 80$) 和 $q$ ($1 \leq q \leq 6 \times 10^5$)，分别表示船上的船舱数量和染染的询问数量。
• 接下来 $n$ 行，第 $i$ 行一个长度为 $n$ 且仅由字符 $0, 1, p$ 组成的字符串 $s_i$，表示题面中概率矩阵的第 $i$ 行。
  • 保证概率矩阵是对称矩阵且对角线全为 $0$。
• 接下来 $q$ 行，第 $i$ 行两个非负整数 $a_i, b_i$ ($0 \leq a_i \leq b_i < 10^9 + 7, b_i \neq 0$)，表示染染第 $i$ 次询问的 $p_i = \frac{a_i}{b_i}$。
  • 保证单个测试点内每组数据中 $q$ 的和不超过 $3 \times 10^6$。
  • 保证单个测试点内只有最多 $5$ 组数据不满足 $n \leq 20$。

输出描述

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

对于每组数据，假设染染第 $i$ 次询问的答案为 $r_i$，你只需要输出一行一个压缩后的非负整数 $R$：

样例

1
3 3
01p
101
p10
0 1
1 1
1 2

13

提示

• 对于第 $1$ 次询问，仅存在一种打通方案 $\{(1,2),(2,3)\}$，答案为 $1$。
• 对于第 $2$ 次询问，存在三种打通方案 $\{(1,2),(2,3)\}, \{(1,2),(1,3)\}, \{(1,3),(2,3)\}$，答案为 $3$。
• 对于第 $3$ 次询问，分别有 $\frac{1}{2}$ 的概率对应前两次询问，答案为 $\frac{1}{2} (1 + 3) = 2$。