每天早上，幼儿园老师都会给孩子们分发玩具。为了保持秩序，每个孩子恰好得到一个玩具。每个孩子可以独自玩耍，也可以与另一个孩子结对玩耍，但前提是这两个孩子互相喜欢。

老师有 $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$ 的测试点。

说明

样例测试点： 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\}$。