题解

#include<bits/stdc++.h>
using namespace std;
#define MAXN 105
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
int xchar() {
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
	if(!x) {putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {putnum(x);putchar(c);}

const int MOD = 1000000007;
int n,m,s,o,k;
void MD(int &x) {if(x>=MOD)x-=MOD;}
struct mat{
	int s[60][60],n,m;
	mat(){memset(s,0,sizeof(s));n=m=0;}
}G,dp0[65],pw0[65],dpl[65],dpr[65];
inline mat operator * (mat a,mat b) {
	mat c; c.n = a.n; c.m = b.m;
	for(int i = 0;i < a.n;i ++) {
		for(int k = 0;k < a.m;k ++) {
			if(a.s[i][k])
			for(int j = 0;j < b.m;j ++) {
				c.s[i][j] = (c.s[i][j] + a.s[i][k]*1ll*b.s[k][j]) % MOD;
			}
		}
	} return c;
}
inline mat operator + (mat a,mat b) {
	for(int i = 0;i < a.n;i ++) {
		for(int j = 0;j < a.m;j ++) {
			MD(a.s[i][j] += b.s[i][j]);
		}
	} return a;
}
inline mat& operator += (mat &a,mat b) {
	for(int i = 0;i < a.n;i ++) {
		for(int j = 0;j < a.m;j ++) {
			MD(a.s[i][j] += b.s[i][j]);
		}
	} return a;
}
int main() {
	n = read(); k = read(); m = read();
	G.n = G.m = n;
	for(int i = 0;i <= k;i ++) dp0[i].n = dp0[i].m = n;
	for(int i = 1;i <= n;i ++) {
		for(int j = 1;j <= n;j ++) {
			char c = getchar();
			while(c == ' ' || c == '\n') c = getchar();
			G.s[i-1][j-1] = c^48;
		}
	}
	mat mt0 = mat();
	mt0.n = mt0.m = n;
	mat mt1 = mt0,ml0 = mat(),mr0 = mat();
	ml0.n = 1; ml0.m = n;
	mr0.n = n; mr0.m = 1;
	for(int i = 0;i < n;i ++) mt1.s[i][i] = 1;
	dp0[1] = G; pw0[1] = dp0[1] * dp0[1];
	for(int i = 2;i <= k;i ++) {
		dp0[i] = pw0[i-1] + G;
		pw0[i] = dp0[i] * dp0[i];
		pw0[i] += pw0[i-1];
	}
	while(m --) {
		s = read(); int S = read();
		o = read(); int T = read();
		if(s > o) swap(s,o);
		for(int i = 1;i <= k;i ++) dpl[i] = ml0,dpr[i] = mr0;
		dpl[s].s[0][S-1] = 1; dpr[o].s[T-1][0] = 1;
		for(int i = s;i <= k;i ++) {
			mat nm = dpl[i] * dp0[i];
			for(int j = i+1;j <= k;j ++) dpl[j] += nm;
		}
		for(int i = o;i <= k;i ++) {
			mat nm = dp0[i] * dpr[i];
			for(int j = i+1;j <= k;j ++) dpr[j] += nm;
		}
		mat as = dpl[o] * dpr[o];
		for(int i = o+1;i <= k;i ++) as += dpl[i] * dpr[i];
		AIput(as.s[0][0],'\n');
	}
	return 0;
}