奶牛 Bessie 被外星人绑架了，现在被困在了一艘外星飞船里！这艘飞船有 $N$ $(1\le N\le 60)$ 个房间，编号为 $1\ldots N$，一些房间对之间有单向门连接（由于外星科技的奇特性，门甚至可能从一个房间连回它自己！）。然而，没有两扇门共享相同的起点和终点。此外，Bessie 还有一个带有编号为 $1\ldots K$ $(1 \le K \le 60)$ 按钮的遥控器。

如果 Bessie 能完成一项奇怪的任务，外星人就会释放她。首先，他们会选择两个房间 $s$ 和 $t$ $(1 \le s, t \le N)$，以及两个数字 $b_s$ 和 $b_t$ $(1 \le b_s, b_t \le K)$。他们会让 Bessie 从房间 $s$ 开始，并立即按下按钮 $b_s$。随后，Bessie 将在按下按钮的同时在飞船中穿行。Bessie 的行动遵循以下规则：

• 在每个房间，按下恰好一个按钮后，她必须选择通过一扇门移动到另一个（可能是同一个）房间，或者停止。
• 一旦 Bessie 按下了一个按钮，除非在此期间她按下了编号更大的按钮，否则她不能再次按下同一个按钮。换句话说，按下编号为 $x$ 的按钮会使其失效，而所有编号 $
• 如果 Bessie 按下了失效的按钮，她会自动失败，外星人将继续关押她。

只有当 Bessie 在房间 $t$ 停止，最后按下的按钮是 $b_t$，且从未按下过失效按钮时，她才会被释放。

Bessie 担心自己无法完成任务。对于 $Q$ $(1\le Q\le 60)$ 次询问，每次询问包含 Bessie 认为可能的 $s, t, b_s$ 和 $b_t$ 的选择，Bessie 想知道有多少种房间和按钮按下的序列能让她获释。请输出答案对 $10^9 + 7$ 取模的结果，因为答案可能非常大。

输入格式

第一行包含 $N, K, Q$。

接下来的 $N$ 行，每行包含 $N$ 个位（均为 0 或 1）。如果第 $i$ 行的第 $j$ 个条目为 1，则表示存在从房间 $i$ 到房间 $j$ 的门，若为 0 则不存在。

随后是 $Q$ 行，每行包含四个整数 $b_s, s, b_t, t$，分别表示起始按钮、起始房间、最终按钮和最终房间。

输出格式

对于每个询问，在单独的行中输出序列的数量，结果对 $10^9+7$ 取模。

样例

样例输入 1

6 3 8
010000
001000
000100
000010
000000
000001
1 1 1 1
3 3 1 1
1 1 3 3
1 1 1 5
2 1 1 5
1 1 2 5
3 1 3 5
2 6 2 6

样例输出 1

1
0
1
3
2
2
0
5

门连接了房间 $1\to 2, 2 \to 3, 3\to 4, 4\to 5$ 以及 $6\to 6$。

对于第一个询问，Bessie 必须在按下第一个按钮后立即停止。

对于第二个询问，答案显然为零，因为无法从房间 3 到达房间 1。

对于第三个询问，Bessie 唯一的选择是按顺序按下按钮 1、2、3，从房间 1 移动到房间 2 再到房间 3。

对于第四个询问，Bessie 的移动路径是固定的，她有三种可能的按钮按下序列：

• $(1,2,3,2,1)$
• $(1,2,1,3,1)$
• $(1,3,1,2,1)$

对于最后一个询问，Bessie 有五种可能的按钮按下序列：

• $(2)$
• $(2,3,2)$
• $(2,3,1,2)$
• $(2,1,3,2)$
• $(2,1,3,1,2)$

样例输入 2

6 4 6
001100
001110
101101
010111
110111
000111
3 2 4 3
3 1 4 4
3 4 4 1
3 3 4 3
3 6 4 3
3 1 4 2

样例输出 2

26
49
29
27
18
22

该测试用例满足除第一个子任务外的所有约束。

样例输入 3

6 10 5
110101
011001
001111
101111
111010
000001
2 5 2 5
6 1 5 2
3 4 8 3
9 3 3 5
5 1 3 4

样例输出 3

713313311
716721076
782223918
335511486
539247783

请确保输出答案对 $10^9+7$ 取模。

子任务

• 在测试用例 4-7 中，$K\le 5$ 且所有询问的 $(b_s,s)$ 相同。
• 在测试用例 8-11 中，每个询问的 $b_s=K-1$ 且 $b_t=K$。
• 在测试用例 12-15 中，$N,K,Q\le 20$。
• 在测试用例 16-23 中，没有额外约束。