题目背景

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

题目描述

有些小孩子玩玩具是自己一个人玩，有些小孩子是成对玩耍。

现在有 $n$ 个小孩子，这 $n$ 个小孩子可以分为 $m$ 对。

有 $k$ 种玩具，要发放给这些小孩子，必须保证在一对内的小孩子拿到的玩具不同。

求一共有多少种发放方案。

因为要发放的天数很多，所以给定 $z$ 组询问，这 $z$ 组询问中 $n,m$ 和对应的对是不变的，变的是 $k$。

输入格式

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

输出格式

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

4 4 1
1 2
2 3
1 3
3 4
3

12

5 10 2
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
5
6

120
720

11 40 1
8 1
4 1
3 8
2 6
9 8
11 5
2 5
2 1
11 4
10 6
11 10
9 7
10 4
6 9
9 10
2 11
6 7
8 2
10 8
3 6
11 9
1 10
4 3
6 11
3 11
4 5
8 7
10 3
11 7
9 2
8 6
2 3
3 7
8 4
9 5
4 9
7 2
5 10
10 2
6 4
15

142679253

提示

样例说明

两个附加样例请见附加文件中的 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 D Przedszkole。