题目背景

星际通信研究员林澈正在测试一张由 $N$ 个通信站组成的实验网络。网络中的每一条链路都可以在“启用”和“关闭”两种状态之间切换。

为了研究随机扰动对网络可靠性的影响，林澈会反复随机选择两个不同的通信站，并切换它们之间链路的状态。由于一个网络能够维持整体通信的基础结构可以用生成树描述，他希望计算经过若干次随机扰动后，网络生成树数量的期望。

题目描述

大师有一棵魔法树。具体地，大师是这么造出来这棵魔法树的。

他先会掏出一个 $N$ 个点 $M$ 条边的简单无向图，保证图上没有重边自环。再给定 $Q$ 次独立询问，每次询问给出整数 $T$，试求对给出图进行 $T$ 次如下操作后得到的图的生成树个数期望，对 $10^9 + 7$ 取模。

1. 随机选择一个二元组 $(a, b)$ 满足 $1 \leq a < b \leq N$；
2. 如果图上没有连接这两个点的边，加入它，否则删除它。

输入格式

第一行三个整数 $N,M,Q$，接下来 $M$ 行每行两个整数 $a_i, b_i$ 表示一条边，接下来 $Q$ 行每行一个整数 $T$ 描述询问。

输出格式

对于每个询问输出一行一个整数表示生成树个数期望，对 $10^9 + 7$ 取模。

样例

样例输入 1

3 2 4
3 1
2 1
0
1
2
3

样例输出 1

1
1
777777784
777777784

样例解释 1

样例一输出的第三行和第四行结果均为 $\frac{7}{9}$ 。

数据范围与提示

本题共有 $10$ 个测试点，每个测试点 $10$ 分。

测试点 $1,2$ 满足 $N \leq 8$; $Q \leq 100$; $T \leq 100$；

测试点 $3,4$ 满足 $Q \leq 100$; $T \leq 100$；

测试点 $5,6,7$ 满足 $Q \leq 100$；

测试点 $8$ 满足 $N \leq 4$; $Q \leq 4$; $T \leq 10^9 + 7$；

对于 $100\%$ 的数据，$2 \leq N \leq 100$; $0 \leq M \leq N^2$; $1 \leq Q \leq 10^5$; $0 \leq T \leq 10^{18}$。保证输入的图不存在重边和自环。