每天早上，幼儿园老师都会给孩子们分发玩具。为了保持秩序，每个孩子恰好得到一个玩具。每个孩子可以独自玩耍，也可以与另一个孩子结对玩耍，但前提是这两个孩子互相喜欢。
老师有 $k$ 种玩具。她想知道，有多少种不同的方式可以将玩具分发给孩子们，使得每两个互相喜欢的孩子都收到不同种类的玩具（这样如果他们结对玩耍，就有两种玩具可以玩）。
输入格式
输入的第一行包含三个整数 $n, m, z$ ($1 \le n \le 100\,000$, $0 \le m \le \min(100\,000, n(n - 1)/2)$, $1 \le z \le 1000$)，分别表示幼儿园里的孩子数量、互相喜欢的孩子对数以及询问次数。
接下来的 $m$ 行指定了互相喜欢的孩子对：每一行包含两个正整数 $a_i$ 和 $b_i$，表示互相喜欢的两个孩子的编号。为简单起见，我们将孩子编号为 $1$ 到 $n$。输入中不会出现重复的对。
最后，$z$ 行包含询问：第 $i$ 行包含一个整数 $k_i$ ($1 \le k_i \le 10^9$)。
输出格式
输出应包含 $z$ 行：第 $i$ 行应包含当有 $k_i$ 种玩具时，分发玩具给孩子们的方法数。结果应模 $10^9 + 7$ 输出（即输出实际数值除以 $10^9 + 7$ 的余数）。
样例
样例输入 1
4 4 1 1 2 2 3 1 3 3 4 3
样例输出 1
12
子任务
测试集由以下子任务组成。在每个子任务中，可能包含多个测试点。在每个子任务中，至少 50% 的分数分配给 $z = 1$ 的测试点。
| 子任务 | 条件 | 分值 |
|---|---|---|
| 1 | $n \le 8, k \le 8, z \le 50$ | 8 |
| 2 | $n \le 15$ | 26 |
| 3 | $m \le 24$ | 33 |
| 4 | 每个孩子恰好喜欢另外两个孩子 | 33 |
说明
样例测试点： 1ocen: $n = 5, m = 10$（所有孩子都互相喜欢），两个询问 $k \in \{5, 6\}$； 2ocen: $n = 11, m = 40$，询问 $k = 15$； 3ocen: $n = 100, m = 15$，五个随机询问 $k \in [10, 100]$； 4ocen: $n = 100, m = 100$，互相喜欢的孩子对为 $i$ 和 $i + 1$（对于 $1 \le i < 100$）以及 $100$ 和 $1$；三个询问 $k \in \{5, 10, 15\}$。