题目描述

给定 $n$ 个点，$m$ 条边的有向无环图。不保证图连通。

$q$ 次询问，每次给出 $k$ 和 $k$ 个互不相同的数 $c_i$，求出如果去掉这 $k$ 个点，整个有向无环图将剩余多少条链。答案对 $10^9+7$ 取模。每次询问独立。

• “链”的定义是：我们设一条长度为 $p$ 的链的路径为 $w_0\to w_1\to\cdots\to w_{p-1}\to w_p$，则应满足 $w_0$ 入度为 $0$，$w_p$ 出度为 $0$。你可以将其理解为一条食物链。

• 两条链是“不同的”，当且仅当它们的长度不同，或者经过的点集不同。

• 需要特别注意的是，删去某些点后新产生的链不计入答案。 例如 $1\to 2\to 3\to 4$ 一图中，有 $1$ 条链 $1\to 2\to 3\to 4$。如果去掉 $2$ 号点，则剩余 $0$ 条链。

输入格式

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

接下来 $m$ 行，每行两个整数 $u,v(u\neq 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

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

232
231
230
231
231
231

提示

「样例 $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$。

「数据范围与约定」

本题采用捆绑测试。

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

对于 $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$ 互不相同。

本题轻微卡常，请注意 IO 优化。

---

「题目来源」

Sweet Round 05 D。
idea & solution：Alex_Wei。