Description

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

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

小 A 定义一条食物链为：从一个入度为 $0$ 的节点 $p_0$ 到一个出度为 $0$ 的节点 $p_w$ 所形成的路径 $p_0\to p_1\to \cdots \to p_{w-1}\to p_w$。注意食物链可能退化成一个点，即 $p_0=p_w$。此外，两种生物之间的食物链可能有多条。

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

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

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

Input Format

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

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

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

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

Output Format

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

Sample

样例 1 输入

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 输出

1
3
0
6
13
7
5

样例 1 说明

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$。

样例 2 输入

233 1
1 2
7
0
1 10
2 10 40
2 15 23
1 1
1 2
2 1 2

样例 2 输出

232
231
230
230
231
231
231

[附加文件](file://down.zip)

Hint

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

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

• Subtask 1（1 point）：给定的图是一条链。
• Subtask 2（14 points）：$n,q\leq 10$。
• Subtask 3（20 points）：$q\leq 10^3$。
• Subtask 4（20 points）：$k=1$。
• Subtask 5（20 points）：$k=2$。
• Subtask 6（25 points）：无特殊限制。

请注意 IO 优化。