题目描述

题目译自 POI XXVII - I etap 「Przedszkole」

有一个 $n$ 个点 $m$ 条边的无向图，每个点从 $1$ 到 $n$ 编号。你有 $k$ 种颜色，要给每个点染色，使得有边相连的两个点颜色不一样。求出染色方案数，对 $10^9+7$ 取模。

输入格式

第一行包含 $3$ 个整数 $n$，$m$ 和 $z$，表示图中点个数，边条数和询问个数。

接下来 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示点 $a_i$ 和 $b_i$ 之间有一条边相连。保证不会有重边和自环。

接下来 $z$ 行，每行包含一个整数 $k_i$，表示你有 $k_i$ 种颜色。

输出格式

对于每组数据，输出你有 $k_i$ 种颜色时的染色方案数，对 $10^9+7$ 取模。

样例

input

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

output

12

附加样例

附加样例参见 prz/prz*.in 和 prz/prz*.out：

• 附加样例 $1$：$n=5,m=10$，两个询问 $k \in {5, 6}$；

• 附加样例 $2$：$n=11,m=40$，一个询问 $k=15$；

• 附加样例 $3$：$n=100,m=15$，$5$ 个询问，$k$ 从 $[10, 100]$ 里面随机；

• 附加样例 $4$：$n=100,m=100$，所有点构成了一个环；三个询问 $k \in {5, 10, 15}$。

数据范围与提示

对于 $100\%$ 的数据，$1 \le n \le 10^5, 0 \le m \le \min(10^5, n(n-1)/2), 1 \le z \le 1000, 1 \le a_i, b_i \le n, 1 \le k_i \le 10^9$。