問題一覧 > 通常問題

No.1141 田グリッド

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 160
作問者 : fuppy_kyoprofuppy_kyopro / テスター : omochana2omochana2
16 ProblemId : 3455 / 出題時の順位表
問題文最終更新日: 2019-10-16 22:43:30

問題文

縦$H$行、横$W$列のグリッドがあります。上から$i$行目、左から$j$列目のマスを$(i, j)$と表します。
これらのマスには非負整数が一つずつ書き込まれています。$(i, j)$には$A_{i,j}$が書き込まれています。
2個の整数$(r_i, c_i)$からなるクエリが$Q$個与えられるので、各クエリに答えてください。$i$個めのクエリは以下のようになります。

  • グリッドの上から$r_i$行目、または左から$c_i$列目にあるマスを全て黒く塗りつぶしたとき、塗りつぶされていない$(H-1) \times (W-1)$マスに書かれた数の積を求めてください。
ただし、答えは非常に大きくなることがあるので$1000000007$で割ったあまりを答えてください。
また、クエリは他のクエリに影響を及ぼさないことに注意してください。つまり、あるクエリで黒く塗りつぶされたマスがその後も塗りつぶされたまま残るわけではありません。

入力

$H\ W$
$A_{1,1}~A_{1,2}~...~A_{1,W}$
:
$A_{H,1}~A_{H,2}~...~A_{H,W}$
$Q$
$r_1~c_1$
:
$r_Q~c_Q$

  • $2 \le H,W \le 10^5$
  • $4 \le H \times W \le 10^5$
  • $0 \le A_{i,j} \le 10^9$
  • $1 \le Q \le 5 \times 10^4$
  • $1 \le r_i \le H$
  • $1 \le c_i \le W$
  • 入力は全て整数である。

出力

$Q$行出力してください。$i$行目には$i$個めのクエリの答えを出力してください。最後に改行してください。

サンプル

サンプル1
入力
2 2
4 3
7 9
1
1 1
出力
9

サンプル2
入力
3 3
7 4 2
9 5 2
9 6 5
2
1 1
3 3
出力
300
1260

サンプル3
入力
3 4
6 8 6 8
3 4 2 9
2 8 6 3
3
3 2
1 2
1 3
出力
15552
1944
5184

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。