题目描述

奶牛 Bessie 外星人绑架了，现在被关在了一艘外星人的飞船里！飞船有 $N$（$1 \leq N \leq 60$）间房间，编号为 $1 \dots N$，其中某些房间之间由单向通过的门所连接（由于使用了奇怪的外星技术，一扇门甚至可能从一间房间通回这间房间本身！）。然而，没有两扇门具有完全相同的出发和到达房间。此外，Bessie 有一个遥控器，上有编号为 $1 \dots K$（$1 \leq K \leq 60$）的按钮。

如果 Bessie 能够完成一个怪异的任务，外星人就会释放她。首先，他们会选择两间房间 $s$ 和 $t$（$1 \leq s,t \leq N$），以及两个整数 $b_s$ 和 $b_t$（$1 \leq b_s,b_t \leq K$）。他们会将 Bessie 放在房间 $s$ 内，并令她立刻按下按钮 $b_s$。然后 Bessie 需要继续在飞船内穿梭，同时按下按钮。有一些 Bessie 的行动需要遵守的规则：

1. 在每间房间内，在按下恰好一个按钮后，她必须选择从某扇门离开去往另一间房间（可能会回到同一间房间）或停止行动。
2. 一旦 Bessie 按下某个按钮，她再次按下这个按钮即为非法，除非在此之间她按下过编号更大的按钮。换句话说，按下编号为 $x$ 的按钮会使得这个按钮变为非法，同时所有编号 $<x$ 的按钮会被重置为合法。
3. 如果 Bessie 按下非法的按钮，任务即失败，外星人就会把她关起来。
4. 仅当 Bessie 停止行动时位于房间 $t$，她最后按下的按钮是 $b_t$，并且没有按下过非法按钮时，Bessie 才会被释放。

Bessie 担心她可能无法完成这一任务。对于 $Q$（$1 \leq Q \leq 60$）个询问，每个询问包含一组 Bessie 认为可能的 $s,t,b_s$ 以及 $b_t$，Bessie 想要知道可以使她得到释放的通过房间与按键序列的数量。由于答案可能非常大，输出对 $10^9+7$ 取模的结果。

输入格式

输入的第一行包含 $N,K,Q$。

以下 $N$ 行每行包含 $N$ 个二进制位（$0$ 或 $1$）。如果从房间 $i$ 到房间 $j$ 存在一扇门，则第 $i$ 行的第 $j$ 位为 $1$，如果没有这样的门则为 $0$。

以下 $Q$ 行，每行包含四个整数 $b_s, s, b_t, t$，分别表示起始按钮、起始房间、结束按钮、结束房间。

输出格式

对 $Q$ 个询问的每一个，在一行内输出操作序列的数量模 $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

text

输出 1 0 1 3 2 2 0 5

text

门连接了房间 $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

text

输出 26 49 29 27 18 22

text

这个测试用例满足除第一个子任务外所有子任务的限制条件。

样例 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

text

输出 713313311 716721076 782223918 335511486 539247783

text

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

数据范围与提示

• 测试点 $4 \sim 7$ 中，$K \leq 5$ 且 $(b_s,s)$ 在所有询问中均相同。
• 测试点 $8 \sim 11$ 中，对所有询问有 $b_s = K-1$ 以及 $b_t = K$。
• 测试点 $12 \sim 15$ 中，$N,K,Q \leq 20$。
• 测试点 $16 \sim 23$ 没有额外限制。