#include #include #include #include #include #include #include #include using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) using ll = long long; using VLL = vector; int constexpr MOD = 1e9+7; int constexpr Max = 2010; int N, K; VLL g[Max]; auto rec(int curr, int parent) -> VLL // 着目している根付き木について、黒く塗られている数->そのパターン数 { VLL ret(1, 1); for(auto ch: g[curr]) { if(ch == parent) { continue; } auto subTree = rec(ch, curr); auto currK = ret.size() - 1; // 自分を除く auto newK = subTree.size() - 1; // 自分を除く VLL nret(currK + newK + 1); rep(iteCurrK, currK + 1) rep(iteNewK, newK + 1) { (nret[iteCurrK + iteNewK] += ret[iteCurrK] * subTree[iteNewK]) %= MOD; } ret = nret; } ret.push_back(1); return ret; } int main() { cin >> N >> K; rep(i, N-1) { int a, b; cin >> a >> b; g[a].push_back(b), g[b].push_back(a); } cout << rec(0, -1)[K] << endl; return 0; }