题目背景

轻策的净水之主——「纯水精灵」洛蒂娅是一个掉水元素角色突破材料的 BOSS。今天你想刷点材料，所以……

题目描述

洛蒂娅所在的水面上有 $n$ 块平台，初始时均未沉没。有 $m$ 对不同的平台彼此相连。洛蒂娅与敌人战斗了 $k$ 个回合。每一回合，她可以选择一些未沉没的平台，让这些平台沉没（可以不选，但不可以让全部平台沉没）。然后她会选择最多的平台，满足任意两块选择的平台之间都相连，在每块平台上召唤一种不同的水之幻形。$k$ 回合结束后，洛蒂娅对敌人的伤害就是每回合召唤的水之幻形数量之和。洛蒂娅想知道，对于她的所有不同选择方案，伤害的总和是多少。两种方案被视为不同当且仅当存在一回合，使得两种方案在这一回合沉没的平台不同，而与召唤水之幻形的平台无关。由于答案可能很大，你需要输出它对 $10^9+7$ 取模的结果。

简要题意：给定无自环无重边的无向图，$k$ 回合中每回合可以删去现有点集的任意真子集，求所有方案中每回合后剩下的图最大团大小之和模 $10^9+7$。

输入格式

第一行输入三个整数 $n,m,k$，分别表示平台数，相连的平台对数，回合数。

接下来 $m$ 行每行两个整数 $x,y$，表示 $x$ 号平台和 $y$ 号平台相连。平台从 $0$ 到 $n-1$ 编号。保证没有自环和重边。

输出格式

输出一行一个整数表示答案。

2 1 2
0 1

14

5 7 100
0 1
1 2
2 3
3 4
0 4
0 3
0 2

969766107

提示

样例解释

有五种不同的方案：

• 第一回合让 $0$ 号平台沉没，第二回合不选，伤害是 $1+1=2$。
• 第一回合让 $1$ 号平台沉没，第二回合不选，伤害是 $1+1=2$。
• 第一回合不选，第二回合让 $0$ 号平台沉没，伤害是 $2+1=3$。
• 第一回合不选，第二回合让 $1$ 号平台沉没，伤害是 $2+1=3$。
• 两回合都不选，伤害是 $2+2=4$。

五种方案的总伤害是 $2+2+3+3+4=14$。

数据范围

本题采用捆绑测试，数据范围符合下表：

对于全部数据，$2\le n\le 28$，$1\le m\le\frac{n(n-1)}{2}$，$1\le k\le 10^9$。

提示

请注意时空限制。

说明

Minecraft OI Round 4 A
idea & solution：鏡音リン check：namespace_std