题目描述

小 A 在研究生态系统的稳定性。

他认为一个生态系统可以被抽象成一张有向无环图 $G=(V,E)$，$V$ 中每个节点代表一种生物，$E$ 中的每一条有向边 $u\to v$ 表示 $u,v$ 之间存在捕食与被捕食的关系：$u$ 被 $v$ 捕食。

小 A 定义一条食物链为：从一个入度为 $0$ 的节点 $p_0$ 到 一个出度为 $0$ 的节点 $p_w$。此外，两种生物之间的食物链可能有多条。

为了测试生态系统的稳定性，小 A 会多次删去若干个节点以模拟特定生物灭绝的情况。他认为生态系统中剩余的食物链越多，则其越稳定。

但由于整个生态系统太复杂了，就算一些生物灭绝后，剩余的食物链数量仍然是巨大的。他想请你帮他求出每次删去一些特定节点后剩余的食物链条数，对 $10^9 + 7$ 取模。注意这个过程会产生新的入度或出度为 $0$ 的节点，但这些新产生的食物链不计入在内。

形式化地，给出一张点数为 $n$，边数为 $m$ 的 DAG。定义路径集合 $S$ 为所有合法路径 $P:p_0\to p_1\to \ldots\to p_{w-1}\to p_w$ 所形成的集合。合法路径可以是一个点，但需要满足 $p_0$ 的入度为 $0$，$p_w$ 的出度为 $0$。$q$ 次询问给出 $k$ 和 $k$ 个互不相同的数 $c_i$，请你求出删去所有 $c_i$ 后，整个 DAG 剩余的合法路径条数，新增的合法路径不计入答案。即求出 $|\{P|P\in S,\forall p_j\in P,p_j\not\in\{c_i\}\}|\bmod 10^9+7$。

询问之间相互独立。

输入格式

第一行两个整数 $n, m$，分别表示点的个数和边的条数。

接下来 $m$ 行，每行两个整数 $u,v(u\not= v)$，表示 $u\to v$ 之间有一条有向边。

第 $m + 2$ 行一个整数 $q$，表示询问个数。

接下来 $q$ 行，每行先是一个整数 $k$，表示去掉的点的个数；然后 $k$ 个整数 $c_i$，表示去掉的点的编号。

输出格式

共 $q$ 行，每行表示该次询问的答案对 $10^9+7$ 取模后的值。

样例

7 14
3 2
4 5
2 5
2 6
3 1
3 5
3 7
3 6
6 4
1 4
6 5
1 6
7 2
7 4
7
3 2 4 6
2 4 6
2 2 5
2 1 4
0
1 4
1 6

1
3
0
6
13
7
5

DAG 如图：

询问 $1$：如果去掉 $2, 4, 6$，则剩余 $1$ 条链：$3 \to 5$。

询问 $2$：如果去掉 $4, 6$，则剩余 $3$ 条链：$3 \to 5$，$3 \to 2 \to 5$，$3 \to 7 \to 2 \to 5$。

询问 $7$：如果去掉 $6$，则剩余 $5$ 条链：$3 \to 5$，$3 \to 2 \to 5$，$3 \to 7 \to 2 \to 5$，$3 \to 1 \to 4 \to 5$，$3 \to 7 \to 4 \to 5$。

233 1
1 2
6
0
1 10
2 10 40
1 1
1 2
2 1 2

232
231
230
231
231
231

见附加文件中的 foodchain3.in

见附加文件中的 foodchain3.ans

该样例满足 Subtask 3 的限制。

见附加文件中的 foodchain4.in

见附加文件中的 foodchain4.ans

该样例满足 Subtask 4 的限制。

见附加文件中的 foodchain5.in

见附加文件中的 foodchain5.ans

该样例满足 Subtask 5 的限制。

数据范围

对于 $100\%$ 的数据，$2\le n\le 2\times 10^3$，$1\le m\le \min(\frac{n\times(n-1)}{2},2\times 10^4)$，$1\le q\le 5\times 10^5$。

所有询问满足 $1\le \sum k\le 2\times 10^6$，$1\le k\le \min(n,15)$，$1\le c_i\le n$，保证 $c_i$ 互不相同。

Subtask 编号	分值	特殊限制
$1$	$1$	给定的图是一条链
$2$	$14$	$n,q\le 10$
$3$	$20$	$q\le 10^3$
$4$		$k=1$
$5$		$k=2$
$6$	$25$	无特殊限制

请注意 IO 优化。