### 问题描述 小齐被外星人绑架，关在一个有 $N$ 个房间的飞船中，每个房间标有 $1\sim N$ 的编号。飞船中有一些门，连接着不同的房间（甚至可能通往同一个房间）。此外，小齐手上有一台遥控器，上面有 $K$ 个按钮，编号为 $1\sim K$。 外星人给出一个任务，选择两个房间 $s$ 和 $t$，以及两个按钮编号 $bs$ 和 $bt$。小齐要按照一定规则在飞船中移动，按下按钮，最终停在房间 $t$ 并按下按钮 $bt$ 才能完成任务。在移动过程中，有以下几个规则： 在每个房间中，小齐可以按下一个按钮后选择继续移动到另一个房间，或者选择停止。 按下按钮后，不能再按下相同编号的按钮，除非在两次按下之间按下了一个编号更高的按钮。 如果按下了无效的按钮，任务将失败。 对于给定的 $Q$ 个任务，每个任务由 $s$、$t$、$bs$ 和 $bt$ 组成，小齐想知道有多少种按规则完成任务的方式。 请你计算每个任务的答案，输出模 $10^9+7$。 ### 输入格式 第一行包含三个整数 $N$、$K$ 和 $Q$。 接下来 $N$ 行，每行包含 $N$ 个二进制数字（$0$ 或 $1$），表示房间之间是否存在门。第 $j$ 行的第 $i$ 个数字为 $1$ 表示从房间 $i$ 可以到达房间 $j$，为 $0$ 表示不能。 接下来 $Q$ 行，每行包含四个整数 $bs$、$s$、$bt$ 和 $t$。 ### 输出格式 输出 $Q$ 行，每行包含一个整数，表示对应任务的答案，输出结果需模 $10^9+7$。 ### 样例输入 ``` 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 0 1 3 2 2 0 5 ``` ### 评测数据规模 $1 \leq N, K, Q \leq 20$。