题解

#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
int n,k,q;
const int MAXN=60+1; 
int dp[2][2][MAXN][MAXN][MAXN],g[2][MAXN][MAXN][MAXN],f[2][MAXN][MAXN][MAXN];
bool e[MAXN][MAXN];
const int MOD=1e9+7;
void add(int& x,int y){
	x+=y;
	if(x>=MOD) x-=MOD;
}
void normal(){
	rb(c,1,k){
		rb(r,1,n){
			rb(a,1,n)rb(b,1,n){
				if(e[b][r]){
					add(g[0][r][a][c],dp[0][0][a][b][c-1]);
				}		
				if(e[r][a]){
					add(f[0][r][b][c],dp[0][0][a][b][c-1]);
				}
			}
			add(f[0][r][r][c],1);
			add(g[0][r][r][c],1);
		}
		rb(i,1,n) rb(j,1,n){
			dp[0][0][i][j][c]=dp[0][0][i][j][c-1];
			rb(r,1,n) add(dp[0][0][i][j][c],1ll*g[0][r][i][c]*f[0][r][j][c]%MOD);
		}
	}
}
int bs,s,bt,t;
int calc(){
	rep(i,2) rep(j,2) if(i+j) memset(dp[i][j],0,sizeof(dp[i][j]));
	memset(g[1],0,sizeof(g[1]));
	memset(f[1],0,sizeof(f[1]));
	rb(c,1,k){
		rb(r,1,n){
			rb(i,1,n){
				if(e[i][r]){
					add(g[1][r][s][c],dp[1][0][s][i][c-1]);
				}
				if(e[r][i]){
					add(f[1][r][t][c],dp[0][1][i][t][c-1]);
				}
			}
		}
		if(c==bs){
			add(g[1][s][s][c],1);
		}
		if(c==bt){
			add(f[1][t][t][c],1);	
		}
		add(dp[1][1][s][t][c],dp[1][1][s][t][c-1]);
		rb(i,1,n){
			add(dp[1][0][s][i][c],dp[1][0][s][i][c-1]);
			add(dp[0][1][i][t][c],dp[0][1][i][t][c-1]);
			rb(r,1,n){
				add(dp[1][0][s][i][c],1ll*g[1][r][s][c]*f[0][r][i][c]%MOD);
				add(dp[0][1][i][t][c],1ll*g[0][r][i][c]*f[1][r][t][c]%MOD);
			}
		}
		rb(r,1,n)
			add(dp[1][1][s][t][c],1ll*g[1][r][s][c]*f[1][r][t][c]%MOD);
	}
	return dp[1][1][s][t][k];
}
int main(){
	cin>>n>>k>>q;
	rb(i,1,n) rb(j,1,n){
		char c;
		cin>>c;
		e[i][j]=c-'0';
	}
	normal(); 
	rb(T,1,q){
		cin>>bs>>s>>bt>>t;
		cout<<calc()<<'\n';
	}		
	return 0;
}