题目描述

给定一个 $n\times n$ 的数组 $A$，其第 $i$ 行第 $j$ 列上的元素为 $A_{i,j}$。

现选定 $k$ 行 $k$ 列从 $A$ 中删除，其它元素的相对位置不变。设删除后得到的数组为 $B$，则 $B$ 的大小为 $(n-k)\times (n-k)$。

对于被删除的 $k$ 行和 $k$ 列，将交点处的元素按原相对顺序构成一个新数组 $C$。

例如，给定 $4\times 4$ 数组 $A$，删除第 $1,3$ 行和 $3,4$ 列，具体过程如下：

$$A = \left( \begin{matrix} 1 & 2 &3&4\\ 5&6&7&8\\ 9&10&11&12\\ 13&14&15&16 \end{matrix} \right) \qquad \begin{matrix} & & & \Downarrow & \Downarrow \\ \Rightarrow & \color{red} 1 & \color{red}2 & \boxed {\color{red}3} & \boxed {\color{red}4}\\ & 5 & 6 & \color{red}7 & \color{red}8\\ \Rightarrow & \color{red} 9 &\color{red}{10} & \boxed{\color{red}11} & \boxed{\color{red}12}\\ & 13 & 14 & \color{red}15 & \color{red}16 \end{matrix} $$

如上，被删除的行、列用双箭头标出。未被标记的元素没有被删除。被标记为红色的元素将被删除。被方框框住的元素即为被删除的行、列交点处的元素。因此，

$$ B = \left( \begin{matrix} 5 & 6 \\ 13 & 14 \end{matrix} \right) \qquad C = \left( \begin{matrix} 3 & 4 \\ 11 & 12 \end{matrix} \right) $$

定义一个对于 $m\times m$ 数组的运算 $f$ 为数组的正对角线上各元素之积减去反对角线上各元素之积。其中，第 $i$ 行第 $i$ 列上的元素在正对角线上，第 $i$ 行第 $m-i + 1$ 列的元素在反对角线上。

例如：

$$ f\left( \begin{matrix} \color{red}1 & 2 & \color{green}3 \\ 4 & \color{blue}5 & 6 \\ \color{green}7 & 8 & \color{red}9 \end{matrix} \right)={\color{red}1\times {\color{blue}5}\times 9}-{\color{green}3\times{\color{blue}5}\times7}=-60 \\ f(B)=f\left( \begin{matrix} \color{red} 5 &\color{green} 6 \\ \color{green} 13 & \color{red}14 \end{matrix} \right)={\color{red}5\times 14}-{\color{green}6\times 13}=-8 \\ f(C)=f\left( \begin{matrix} \color{red} 3 &\color{green} 4 \\ \color{green} 11 & \color{red}12 \end{matrix} \right)={\color{red}3\times 12}-{\color{green}4\times 11}=-8 $$

如上，红色表示该元素在正对角线上，绿色表示该元素在反对角线上，蓝色表示该元素既在正对角线上，又在反对角线上。

对于 $n\times n$ 数组 $A$ 和删除的 $k$ 行 $k$ 列，定义代数瓜子式为 $f(B)\times f(C)$ 的值。其中数组 $B,C$ 和运算 $f$ 的定义如上。

现给定 $n\times n$ 数组 $A$，$q$ 次询问若删除给定的 $k$ 行 $k$ 列，所得代数瓜子式对 $(10^9+7)$ 取模的值。

这里的“取模”后的值总是为非负数。如果你正在使用 C++ 编写代码，你可以使用以下方法取模：

const int mod = 1000000007;
......

// 在某次运算中，假设要对 ans 变量取模
ans = ((ans % mod) + mod) % mod;

......

输入格式

第一行输入两个以空格分隔的正整数 $n,q$。

接下来 $n$ 行，每行输入 $n$ 个以空格分隔的整数，表示数组 $A$。

接下来 $q$ 行，每行一组询问，询问格式如下：

• 首先输入一个正整数 $k$，表示删除的行、列的数量。
• 接下来按递增顺序输入 $k$ 个互不相同的正整数，表示要删除的行的编号。
• 接下来按递增顺序输入 $k$ 个互不相同的正整数，表示要删除的列的编号。

输出格式

对于每组询问，输出一行一个整数表示答案。

4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2 1 3 3 4
2 2 3 1 2

64
48

4 3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 1 1
1 2 4
3 1 2 3 2 3 4

0
0
0

5 7
3 1 4 1 5
9 2 6 5 3
5 3 5 8 9
7 9 3 2 3
8 4 6 2 6
2 1 2 3 4
3 1 2 3 2 3 4
2 1 3 1 3
3 1 3 5 1 3 5
2 1 4 3 5
3 1 3 4 2 4 5
1 1 1

999994715
540
0
4510
198
999997991
0

提示

样例 1 解释

此样例的第一组询问即为题目描述中的例子。

$$ B = \left( \begin{matrix} 5 & 6 \\ 13 & 14 \end{matrix} \right) \qquad C = \left( \begin{matrix} 3 & 4 \\ 11 & 12 \end{matrix} \right) \\ f(B)=f\left( \begin{matrix} \color{red} 5 &\color{green} 6 \\ \color{green} 13 & \color{red}14 \end{matrix} \right)={\color{red}5\times 14}-{\color{green}6\times 13}=-8 \\ f(C)=f\left( \begin{matrix} \color{red} 3 &\color{green} 4 \\ \color{green} 11 & \color{red}12 \end{matrix} \right)={\color{red}3\times 12}-{\color{green}4\times 11}=-8 $$

则代数瓜子式的值为 $f(B)\times f(C)=64$。

对于第二组询问，有：

$$ B = \left( \begin{matrix} 3 & 4 \\ 15 & 16 \end{matrix} \right) \qquad C = \left( \begin{matrix} 5 & 6 \\ 9 & 10 \end{matrix} \right) \\ f(B)=f\left( \begin{matrix} \color{red} 3 &\color{green} 4 \\ \color{green} 15 & \color{red}16 \end{matrix} \right)={\color{red}3\times 16}-{\color{green}4\times 15}=-12 \\ f(C)=f\left( \begin{matrix} \color{red} 5 &\color{green} 6 \\ \color{green} 9 & \color{red}10 \end{matrix} \right)={\color{red}5\times 10}-{\color{green}6\times 9}=-4 $$

则代数瓜子式的值为 $f(B)\times f(C)=48$。

样例 2 解释

注意对于所有 $1\times 1$ 数组 $A$，都有 $f(A)=0$，因此该样例的每一组输出均为 $0$。

样例 3 解释

请注意输出答案对 $(10^9+7)$ 取模的值。

此样例的第 $1,2$ 组询问满足特殊性质 C。

此样例的第 $3,4$ 组询问满足特殊性质 B。

此样例的第 $1,3,5$ 组询问满足特殊性质 A。

数据范围与约定

对于全部数据，满足 $1\le k< n\le 600, 1\le q\le 600,0\le A_{i,j}<10^5$。各测试点的详细数据范围见下表。

测试点	$n$	$q$	特殊性质
$1\sim 4$	$\le 100$		无
$5\sim 8$	$\le 600$		A
$9\sim 11$			B
$12\sim 14$			C
$15\sim 20$			无

特殊性质 A：保证 $k=2$。

特殊性质 B：保证第 $i$ 行和第 $i$ 列要么被同时删除，要么都不删除。

特殊性质 C：保证被删除的行、列的交恰好为原数组的一个子数组。