問題一覧 > 通常問題

No.1141 Ta Grid

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 211
作問者 : fuppy_kyopro / テスター : omochana2
お気に入りにしたユーザー ProblemId : 3455 / 自分の提出
問題文最終更新日: 2019-10-16 22:43:30
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 259 (順位表) の他の問題:

Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i, j)$.
Each of these cells contains one non-negative integer. The cell $(i, j)$ contains $A_{i,j}$.
You are given $Q$ queries, each consisting of two integers $(r_i, c_i)$. Answer each query. The $i$-th query is as follows.

  • When all cells in the $r_i$-th row from the top or the $c_i$-th column from the left of the grid are painted black, find the product of the numbers written in the $(H-1) \times (W-1)$ cells that are not painted.
Since the answer can be very large, output it modulo $1000000007$.
Also, note that queries do not affect other queries. That is, cells painted black in one query do not remain painted afterward.

Input

$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$
  • All inputs are integers.

Output

Output $Q$ lines. On the $i$-th line, output the answer to the $i$-th query. Print a newline at the end.

Sample

Sample 1
Input
2 2
4 3
7 9
1
1 1
Output
9

Sample 2
Input
3 3
7 4 2
9 5 2
9 6 5
2
1 1
3 3
Output
300
1260

Sample 3
Input
3 4
6 8 6 8
3 4 2 9
2 8 6 3
3
3 2
1 2
1 3
Output
15552
1944
5184

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