問題一覧 > 通常問題

No.1141 田グリッド

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 205
作問者 : fuppy_kyopro / テスター : omochana2
19 ProblemId : 3455 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-10-16 22:43:30

問題文

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

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

入力

H W
A1,1 A1,2 ... A1,W
:
AH,1 AH,2 ... AH,W
Q
r1 c1
:
rQ cQ

  • 2≤H,W≤105
  • 4≤H×W≤105
  • 0≤Ai,j≤109
  • 1≤Q≤5×104
  • 1≤ri≤H
  • 1≤ci≤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もしくは右上の雲マークをクリックしてアカウントを作成してください。