考虑剥路径最大值 dp，设 \(f_{k, i, j}\) 为 \(i \to j\) 中按的最大的按钮 \(\le k\) 的方案数。转移枚举按下最大值按钮的点 \(w\)，有：
\[f_{k, i, j} = \sum\limits_{(u, w), (w, v) \in E} f_{k - 1, i, u} f_{k - 1, v, j}
\]
在外层枚举 \(w\)，设 \(g_i\) 为起点为 \(i\) 的方案数，\(h_i\) 为起点为 \(j\) 的方案数。拆式子之后有：
\[f_{k, i, j} = \sum g_i h_j
\]
但是这样有个问题。不能保证 \(s \to t\) 时第一次和最后一次按下的按钮是什么。考虑对于每组询问添加虚点 \(n + i\)，只有起点或终点恰好按下 \(b_s\) 或 \(b_t\) 时，\(g_i\) 或 \(h_j\) 才有 \(1\) 的贡献。dp 对应的含义加上了按下按钮的限制。
时间复杂度 \(O(nm(n + q)^2)\)。
code
// Problem: P7155 [USACO20DEC] Spaceship P
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7155
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 125;
const ll mod = 1000000007;
ll n, m, q, f[maxn][maxn][maxn], g[maxn], h[maxn];
char s[maxn][maxn];
struct node {
ll x, y, s, t;
} a[maxn];
inline void upd(ll &x, ll y) {
((x += y) >= mod) && (x -= mod);
}
void solve() {
scanf("%lld%lld%lld", &n, &m, &q);
for (int i = 1; i <= n; ++i) {
scanf("%s", s[i] + 1);
}
for (int i = 1; i <= q; ++i) {
scanf("%lld%lld%lld%lld", &a[i].x, &a[i].s, &a[i].y, &a[i].t);
}
for (int k = 1; k <= m; ++k) {
for (int i = 1; i <= n + q; ++i) {
for (int j = 1; j <= n + q; ++j) {
f[k][i][j] = f[k - 1][i][j];
}
}
for (int v = 1; v <= n; ++v) {
mems(g, 0);
mems(h, 0);
g[v] = h[v] = 1;
for (int i = 1; i <= q; ++i) {
g[n + i] = (a[i].x == k && a[i].s == v);
h[n + i] = (a[i].y == k && a[i].t == v);
}
for (int i = 1; i <= n + q; ++i) {
for (int u = 1; u <= n; ++u) {
if (s[u][v] == '1') {
upd(g[i], f[k - 1][i][u]);
}
if (s[v][u] == '1') {
upd(h[i], f[k - 1][u][i]);
}
}
}
for (int i = 1; i <= n + q; ++i) {
for (int j = 1; j <= n + q; ++j) {
upd(f[k][i][j], g[i] * h[j] % mod);
}
}
}
}
for (int i = 1; i <= q; ++i) {
printf("%lld\n", f[m][n + i][n + i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}