luogu

```cpp
#include <cstdio>

#define rep( i, l, r ) for ( int i = l, rpbound##i = r; i <= rpbound##i; ++i )
#define per( i, r, l ) for ( int i = r, rpbound##i = l; i >= rpbound##i; --i )

const int MAXN = 60, MOD = 1e9 + 7;
int n, m, q, f[MAXN + 5][MAXN * 2 + 5][MAXN * 2 + 5];
int lef[MAXN * 2 + 5], rig[MAXN * 2 + 5];
char adj[MAXN + 5][MAXN + 5];
struct Query { int bs, s, bt, t; } qry[MAXN + 5];

inline int mul( const long long a, const int b ) { return a * b % MOD; }
inline int add( int a, const int b ) { return ( a += b ) < MOD ? a : a - MOD; }
inline void addeq( int& a, const int b ) { ( a += b ) >= MOD && ( a -= MOD ); }

int main() {
	scanf( "%d %d %d", &n, &m, &q );
	rep ( i, 1, n ) {
		scanf( "%s", adj[i] + 1 );
		rep ( j, 1, n ) adj[i][j] ^= '0';
	}
	rep ( i, 1, q ) {
		scanf( "%d %d %d %d", &qry[i].bs, &qry[i].s, &qry[i].bt, &qry[i].t );
	}
	rep ( h, 1, m ) {
		int ( *fcur )[MAXN * 2 + 5]( f[h] );
		int ( *flas )[MAXN * 2 + 5]( f[h - 1] );
		rep ( i, 1, n + q ) rep ( j, 1, n + q ) fcur[i][j] = flas[i][j];
		rep ( k, 1, n ) {
			rep ( i, 1, n ) lef[i] = rig[i] = 0;
			lef[k] = rig[k] = 1;
			rep ( i, 1, q ) {
				lef[n + i] = qry[i].bs == h && qry[i].s == k;
				rig[n + i] = qry[i].bt == h && qry[i].t == k;
			}
			rep ( i, 1, n + q ) rep ( j, 1, n ) if ( adj[j][k] ) {
				addeq( lef[i], flas[i][j] );
			}
			rep ( i, 1, n ) rep ( j, 1, n + q ) if ( adj[k][i] ) {
				addeq( rig[j], flas[i][j] );
			}
			rep ( i, 1, n + q ) rep ( j, 1, n + q ) {
				addeq( fcur[i][j], mul( lef[i], rig[j] ) );
			}
		}
	}
	rep ( i, 1, q ) printf( "%d\n", f[m][n + i][n + i] );
	return 0;
}