P6662 [POI 2019/2020 R1] Przedszkole / 幼儿园

幼儿园的早上，老师们要给小孩子发玩具。

有些小孩子玩玩具是自己一个人玩，有些小孩子是成对玩耍。 现在有 $n$ 个小孩子，这 $n$ 个小孩子可以分为 $m$ 对。 有 $k$ 种玩具，要发放给这些小孩子，必须保证在一对内的小孩子拿到的玩具不同。 求一共有多少种发放方案。 因为要发放的天数很多，所以给定 $z$ 组询问，这 $z$ 组询问中 $n,m$ 和对应的对是不变的，变的是 $k$。

第一行三个整数 $n,m,z$ 代表小孩子数，成对数和询问数。 这 $n$ 个小朋友编号为 $1$ 到 $n$。 接下来 $m$ 行每行两个整数代表一对小朋友。 接下来 $z$ 行每行一个整数 $k$ 代表一组询问。

$z$ 行每行一个整数代表发放方案数。 答案对 $10^9+7$ 取模。

#### 样例说明 两个附加样例请见附加文件中的 sample 1/2.in 和 sample 1/2.out。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（8 pts）：$n,k \le 8$，$z \le 50$。 - Subtask 2（26 pts）：$n \le 15$。 - Subtask 3（33 pts）：$m \le 24$。 - Subtask 4（33 pts）：一个小朋友恰好在两对小朋友。 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le m \le \min(10^5,\dfrac{n^2-n}{2})$，$1 \le z \le 1000$，$1 \le k \le 10^9$。 对于其中 $50\%$ 的数据，$z=1$。 #### 说明 翻译自 [POI 2019](https://sio2.mimuw.edu.pl/c/oi27-1/dashboard/) D [Przedszkole](https://sio2.mimuw.edu.pl/c/oi27-1/p/prz/)。