public class FoxAndSouvenir
{
	static final long mod = 1000000009, primitiveRoot = 13;

	long power(long b, long exp)
	{
		long ret = 1;
		while(exp > 0)
		{
			if(exp % 2 == 1) ret = (ret * b) % mod;
			b = (b * b) % mod;
			exp /= 2;
		}
		return ret;
	}

	int N;
	long r, invN;
	long [] a, invA; // a[i] = r^i
	long [] b, invB; // b[i] = 1 + r^i

	void prepare()
	{
		N = 3507; // we should have (mod-1) % N == 0, N % 2 == 1
		r = power(primitiveRoot, (mod - 1) / N);
		invN = power(N, mod - 2);
		a = new long[N]; invA = new long[N];
		b = new long[N]; invB = new long[N];
		for(int i = 0; i < N; i++)
		{
			a[i] = power(r, i);
			invA[i] = power(a[i], mod - 2);
			b[i] = (a[i] + 1) % mod;
			invB[i] = power(b[i], mod - 2);
		}
	}

	public int[] waysToBuy(int n, int m, int[] price, int[] xMin, int[] xMax, int[] yMin, int[] yMax, int[] require)
	{
		prepare();
		int [][][] s = new int[n][m][N];
		int [][][] invS = new int[n][m][N];
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
			{
				int id = 0;
				for(int k = 0; k < N; k++)
				{
					s[i][j][k] = (int)(price[i*m+j] == 0 ? 1 : b[id]);
					invS[i][j][k] = (int)(price[i*m+j] == 0 ? 1 : invB[id]);
					id += price[i*m+j];
					if(id >= N)
						id -= N;
					if(i > 0)
					{
						s[i][j][k] = (int)(((long)s[i][j][k] * s[i-1][j][k]) % mod);
						invS[i][j][k] = (int)(((long)invS[i][j][k] * invS[i-1][j][k]) % mod);
					}
					if(j > 0)
					{
						s[i][j][k] = (int)(((long)s[i][j][k] * s[i][j-1][k]) % mod);
						invS[i][j][k] = (int)(((long)invS[i][j][k] * invS[i][j-1][k]) % mod);
					}
					if(i > 0 && j > 0)
					{
						s[i][j][k] = (int)(((long)s[i][j][k] * invS[i-1][j-1][k]) % mod);
						invS[i][j][k] = (int)(((long)invS[i][j][k] * s[i-1][j-1][k]) % mod);
					}
				}
			}
		int nQuery = xMin.length;
		int[] ret = new int[nQuery];
		for(int i = 0; i < nQuery; i++)
		{
			long v = 0;
			int id = 0;
			for(int k = 0; k < N; k++)
			{
				long t = invA[id];
				id += require[i];
				if(id >= N) id -= N;
				t = (t * s[xMax[i]][yMax[i]][k]) % mod;
				if(xMin[i] > 0)
					t = (t * invS[xMin[i]-1][yMax[i]][k]) % mod;
				if(yMin[i] > 0)
					t = (t * invS[xMax[i]][yMin[i]-1][k]) % mod;
				if(xMin[i] > 0 && yMin[i] > 0)
					t = (t * s[xMin[i]-1][yMin[i]-1][k]) % mod;
				v = (v + t) % mod;
			}
			v = (v * invN) % mod;
			ret[i] = (int) v;
		}
		return ret;
	}
}