<h1>CF1097G</h1>
题意大概是给 $n$ 个点的树，定义 $f(S)$ 表示 $S$ 中所有的点构成的斯坦纳树的大小。求
$$\sum_{S \subseteq [1,2,\cdots,n],S \neq \emptyset} f(S)^k$$
解：首先看到 $k$ 次方和发现不太好求，我们可以拆成斯特林数的形式：
$$x^k = \sum_{i=0}^k i! (^x_i) \{^k_i\}$$
其中 $\{^a_b\}$ 表示第二类斯特林数，组合意义是将 $a$ 个有标号的求放进 $b$ 个无标号的箱子的方案数。
考虑组合意义，枚举最后一个球怎么放可以写出递推方程：
$$\{^n_m\} = m\{^{n-1}_ m\} + \{^{n-1}_ {m-1}\}$$
边界状态为 $\{^0_0\} = 1$
然后我们考虑为什么对 $x^k$ 的展开是对的：我们只需要考虑组合意义是否相同。
左边的组合意义：有 $k$ 个球，$x$ 中颜色，染色方案是 $x^k$
右边的组合意义：首先将相同颜色的球锁起来，枚举有多少种不同颜色的球 $i$，首先要从这 $x$ 种颜色选出 $i$ 中互不相同的颜色 ($(^x_i)$)，然后要将这个 $k$ 个球染上 $i$ 种颜色（相当于将 $k$ 个 有标号的球放入 $i$ 个有标号的箱子里，也就是 $i! \{^k_i\}$）
所以左右两边组合意义相同，等式成立。
然后代入原式可以得到
$$\sum_{S} \sum_{i=0}^k i! (^{f(S)}_ i) \{^k_i\}$$
$$\sum_{i=0}^k i! \{^k_i\} \sum_{S} (^{f(S)}_ i)$$
发现我们只需要算 $\sum_{S} (^{f(S)}_ i)$ 了，这个式子其实计算的是所有点集的斯坦纳树中选择 $i$ 条边的方案数，这个树形背包做就好了。
设 $f_{i,j}$ 表示以 $i$ 为根的子树内选择了 $j$ 条边的方案数，转移时考虑：
- 不选这个子树
- 只选这个子树
- 同时选这个子树和其他子树
就可以了。最后代入原式计算即可。
/*
* Author: RainAir
* Time: 2019-08-03 20:00:00
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 1e5 + 5;
const int ha = 1e9 + 7;
std::vector<int> G[MAXN];
int n,K;
int fac[205],S205;
int fMAXN,sz[MAXN],ans[MAXN];
inline void dfs(int v,int fa=0){
sz[v] = 1;fv = 1;
for(auto x:G[v]){
if(x == fa) continue;
dfs(x,v);
static int tmp[500+5];CLR(tmp,0);
FOR(i,0,(int)sz[v]-1){
if(i > K) break;
FOR(j,0,(int)sz[x]-1){
if(i+j > K) break;
(tmp[i+j] += fv*fx%ha) %= ha;
(tmp[i+j+1] += fv*fx%ha) %= ha;
(ans[i+j] += fv*fx%ha) %= ha;
(ans[i+j+1] += fv*fx%ha) %= ha;
}
}
FOR(i,0,K) fv = (fv + tmp[i] + fx + ((i == 0) ? 0 : fx))%ha;
sz[v] += sz[x];
}
}
signed main(){
scanf("%lld%lld",&n,&K);
FOR(i,1,n-1){
int u,v;scanf("%lld%lld",&u,&v);
G[u].pb(v);G[v].pb(u);
}
S0 = 1;fac[0] = 1;
FOR(i,1,K){
fac[i] = 1llfac[i-1]i%ha;
FOR(j,1,K){
Si = (1llSi-1j%ha+Si-1) % ha;
}
}
dfs(1);int res = 0;
FOR(i,0,K){
(res += 1llfac[i]SK%ha*ans[i]%ha) %= ha;
}
printf("%lldn",res);
return 0;
}
