#include using namespace std; #ifdef LOCAL #include "debug.h" #else #define DEBUG(...) #endif template > constexpr T power(T a, long long n, Op op = Op(), T e = {1}) { assert(n >= 0); while (n) { if (n & 1) e = op(e, a); if (n >>= 1) a = op(a, a); } return e; } template struct modular { using m = modular; static constexpr unsigned mod = M; unsigned v; modular(long long x = 0) : v((x %= mod) < 0 ? x + mod : x) {} m operator-() const { return m() -= *this; } m& operator+=(m b) { if ((int)(v += b.v - mod) < 0) v += mod; return *this; } m& operator-=(m b) { if ((int)(v -= b.v) < 0) v += mod; return *this; } m& operator*=(m b) { v = (uint64_t)v * b.v % mod; return *this; } m& operator/=(m b) { return *this *= power(b, mod - 2); } friend m operator+(m a, m b) { return a += b; } friend m operator-(m a, m b) { return a -= b; } friend m operator*(m a, m b) { return a *= b; } friend m operator/(m a, m b) { return a /= b; } friend bool operator==(m a, m b) { return a.v == b.v; } }; using mint = modular; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int h, w; cin >> h >> w; vector a(h, vector(w)); for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { cin >> a[i][j].v; } } auto c00 = a, c01 = a, c10 = a, c11 = a; for (int i = 0; i < h; ++i) { for (int j = 1; j < w; ++j) { c00[i][j] *= c00[i][j - 1]; } for (int j = w; j-- > 1; ) { c01[i][j - 1] *= c01[i][j]; } } for (int j = 0; j < w; ++j) { for (int i = 1; i < h; ++i) { c00[i][j] *= c00[i - 1][j]; c01[i][j] *= c01[i - 1][j]; } } for (int j = 0; j < w; ++j) { for (int i = h; i-- > 1; ) { c10[i - 1][j] *= c11[i][j]; c11[i - 1][j] *= c11[i][j]; } } for (int i = 0; i < h; ++i) { for (int j = 1; j < w; ++j) { c10[i][j] *= c10[i][j - 1]; } for (int j = w; j-- > 1; ) { c11[i][j - 1] *= c11[i][j]; } } DEBUG(c00); DEBUG(c01); DEBUG(c10); DEBUG(c11); int q; cin >> q; while (q--) { int i, j; cin >> i >> j; --i, --j; mint res = 1; if (i and j) { res *= c00[i - 1][j - 1]; } if (i and j + 1 < w) { res *= c01[i - 1][j + 1]; } if (i + 1 < h and j) { res *= c10[i + 1][j - 1]; } if (i + 1 < h and j + 1 < w) { res *= c11[i + 1][j + 1]; } cout << res.v << '\n'; } }