「MCOI-04」纯水精灵

轻策的净水之主——「纯水精灵」洛蒂娅是一个掉水元素角色突破材料的 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$。 #### 数据范围 本题采用捆绑测试，数据范围符合下表： | 测试点编号 | $n\le$ | $k\le$ | 得分 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $1$ | $10$ | | $2$ | $16$ | $100$ | $10$ | | $3$ | $20$ | $100$ | $20$ | | $4$ | $26$ | $1$ | $20$ | | $5$ | $26$ | $10^9$ | $20$ | | $6$ | $28$ | $10^9$ | $20$ | 对于全部数据，$2\le n\le 28$，$1\le m\le\frac{n(n-1)}{2}$，$1\le k\le 10^9$。 #### 提示 请注意时空限制。 #### 说明 [Minecraft OI Round 4](https://www.luogu.com.cn/contest/33344) A idea & solution：鏡音リン check：namespace_std