#![allow(dead_code, unused_imports, unused_macros, non_snake_case)] fn main() { input! { H: usize, W: usize, A: [[i64; W]; H], Q: usize, queries: [(Usize1, Usize1); Q], } let mut prod00 = vec![vec![1; W + 2]; H + 2]; for i in 0 .. H { for j in 0 .. W { prod00[i + 1][j + 1] = prod00[i + 1][j] * A[i][j] % MOD; } } for j in 0 .. W { for i in 0 .. H { prod00[i + 1][j + 1] = prod00[i][j + 1] * prod00[i + 1][j + 1] % MOD; } } let mut prod01 = vec![vec![1; W + 2]; H + 2]; for i in 0 .. H { for j in (0 .. W).rev() { prod01[i + 1][j + 1] = prod01[i + 1][j + 2] * A[i][j] % MOD; } } for j in 0 .. W { for i in 0 .. H { prod01[i + 1][j + 1] = prod01[i][j + 1] * prod01[i + 1][j + 1] % MOD; } } let mut prod10 = vec![vec![1; W + 2]; H + 2]; for i in 0 .. H { for j in 0 .. W { prod10[i + 1][j + 1] = prod10[i + 1][j] * A[i][j] % MOD; } } for j in 0 .. W { for i in (0 .. H).rev() { prod10[i + 1][j + 1] = prod10[i + 2][j + 1] * prod10[i + 1][j + 1] % MOD; } } let mut prod11 = vec![vec![1; W + 2]; H + 2]; for i in 0 .. H { for j in (0 .. W).rev() { prod11[i + 1][j + 1] = prod11[i + 1][j + 2] * A[i][j] % MOD; } } for j in 0 .. W { for i in (0 .. H).rev() { prod11[i + 1][j + 1] = prod11[i + 2][j + 1] * prod11[i + 1][j + 1] % MOD; } } for &(r, c) in &queries { let mut ans = 1; ans = ans * prod00[r][c] % MOD; ans = ans * prod01[r][c + 2] % MOD; ans = ans * prod10[r + 2][c] % MOD; ans = ans * prod11[r + 2][c + 2] % MOD; say(ans); } } type Int = i64; // const MOD: Int = 998244353; const MOD: Int = 1_000_000_007; const INF: Int = 1_000_000_000_000_000_000; const YESNO: [&'static str; 2] = ["Yes", "No"]; use proconio::{input, marker::{Chars, Bytes, Usize1}}; use std::*; use std::ops::*; use collections::*; // (BTree|Hash)(Set|Map), BinaryHeap, VecDeque, LinkedList use cmp::{self, Reverse}; // cmp::{min, max} fn yes() { println!("{}", YESNO[0]); } fn no() { println!("{}", YESNO[1]); } fn yesno(c: bool) { println!("{}", if c { YESNO[0] } else { YESNO[1] }); } fn say(x: T) -> T { println!("{}", x); x } fn neighbor4(i: usize, j: usize, h: usize, w: usize, mut f: F) { if i > 0 { (f)(i - 1, j); } if i < h - 1 { (f)(i + 1, j); } if j > 0 { (f)(i, j - 1); } if j < w - 1 { (f)(i, j + 1); } } trait MyItertools : Iterator + Sized { fn to_vec(self) -> Vec { self.collect::>() } fn to_vec_rev(self) -> Vec { let mut v = self.collect::>(); v.reverse(); v } fn tally(self) -> HashMap where Self::Item: Copy + Eq + hash::Hash { let mut counts = HashMap::new(); self.for_each(|item| *counts.entry(item).or_default() += 1 ); counts } fn count_if bool>(self, predicate: P) -> usize { self.map(predicate).filter(|&x| x ).count() } fn implode(self, sep: &str) -> String where Self::Item: std::string::ToString { self.map(|x| x.to_string()).to_vec().join(sep) } fn mex(self, gen: impl IntoIterator) -> Self::Item where Self::Item: Ord { let mut v = self.collect::>(); v.sort(); v.dedup(); let mut it = v.into_iter(); gen.into_iter().find(|a| if let Some(x) = it.next() { a != &x } else { true }).unwrap() } } impl MyItertools for T where T: Iterator + Sized {} trait MyOrd : PartialOrd + Sized { fn chmax(&mut self, mut rhs: Self) -> bool { if self < &mut rhs { *self = rhs; true } else { false } } fn chmin(&mut self, mut rhs: Self) -> bool { if self > &mut rhs { *self = rhs; true } else { false } } } impl MyOrd for T {}