小 D 正在学习图论，你需要帮她完成课后习题。
小 D 今天学习了导出子图的定义：一个点集 V′ 的导出子图 G′=(V′,E′)，其中 E′ 为 E 中所有两端点都在 V′ 中的边。
给定一张包含 n 个点，m 条边的简单无向图 G=(V,E)，以及一个指数 k。
你需要求出所有 2n 个集合的导出子图的边数的 k 次方和对 109+7 取模的值。
输入格式
第一行三个正整数 n,m,k。
接下来 m 行，每行两个正整数 ui,vi，表示一条边。
输出格式
一个正整数，表示答案对 109+7 取模的值。
4 5 2
1 2
2 3
3 4
4 1
2 4
56
样例 1 解释
有 5 张导出子图的边数为 1。有 2 张导出子图的边数为 2。有 2 张导出子图的边数为 3。有 1 张导出子图的边数为 5。
故答案为 5×12+2×22+2×32+1×52=56。
样例 2
见选手目录下的 splitham/graph2.in 和 splitham/graph2.ans。
该样例数据范围满足测试点 4。
样例 3
见选手目录下的 splitham/graph3.in 和 splitham/graph3.ans。
该样例数据范围满足测试点 7。
数据范围
本题共 10 个测试点，全部测试点满足 1≤n,m≤105，1≤k≤3，1≤ui,vi≤n，u_i\not=v_i。
| 测试点 |
n≤ |
m≤ |
k= |
特殊性质 |
| 1 |
105 |
105 |
1 |
无 |
| 2 |
105 |
n−1 |
2 |
A |
| 3 |
105 |
n−1 |
2 |
B |
| 4 |
105 |
105 |
2 |
无 |
| 5 |
12 |
50 |
3 |
无 |
| 6 |
100 |
103 |
3 |
无 |
| 7 |
2048 |
105 |
3 |
无 |
| 8 |
105 |
n−1 |
3 |
A |
| 9 |
105 |
n−1 |
3 |
B |
| 10 |
105 |
105 |
3 |
无 |
特殊性质 A：ui=i，vi=i+1。
特殊性质 B：ui=1，vi=i+1。