#include using namespace std; #define int long long long long gcd(long long a,long long b){ return b ? gcd(b,a%b) : a; } long long lcm(long long a,long long b){ return a / gcd(a,b) * b; } long long mul(long long a,long long b,const long long mod){ return b?(mul(a*2,b/2,mod)+(b&1?a:0))%mod:0; } long long bpow(long long a,long long b,const long long mod){ return (b?bpow(a*a%mod,b/2,mod)*(b&1?a:1):1)%mod; } long long inv(long long a,const long long mod){ return bpow(a,mod-2,mod); } // to overflow /*long long bpow(long long a,long long b,const long long mod){ return (b?mul(bpow(mul(a,a,mod),b/2,mod),(b&1?a:1),mod):1)%mod; }*/ class mInt{ public: static const long long mod = 1000000007; long long v; mInt():v(0){} mInt(long long v):v((v%mod+mod)%mod){} }; mInt& operator += (mInt &a,mInt b){ return a = a.v + b.v; } mInt& operator -= (mInt &a,mInt b){ return a = a.v - b.v; } mInt& operator *= (mInt &a,mInt b){ return a = a.v * b.v; } mInt& operator /= (mInt &a,mInt b){ return a = a.v * inv(b.v,mInt::mod); } mInt operator + (mInt a,mInt b){ return a += b; } mInt operator - (mInt a,mInt b){ return a -= b; } mInt operator * (mInt a,mInt b){ return a *= b; } mInt operator / (mInt a,mInt b){ return a /= b; } ostream& operator<<(ostream& os, const mInt& x){ return os << x.v; } class Tree{ public: Tree(){} //[0,n) int n,logn,root; vector> child; vector> parent; vector> edges; vector depth; Tree(int n_,vector> es,int root) : root(root){ edges = es; n = n_; logn = 0; while(n_){ ++logn; n_ /= 2; } parent.resize(logn,vector(n,-1)); depth.resize(n,-1); child.resize(n); vector> g(n); for( auto e : es ){ g[e.first].push_back(e.second); g[e.second].push_back(e.first); } dfs(g); gen_lca(); verify(); } bool verify(){ for(int i = 0 ; i < n ; i++) assert( depth[i] != -1 ); } int lca(int x,int y){ if( depth[x] < depth[y] )swap(x,y); int d = depth[x] - depth[y]; for(int i = 0 ; i < logn ; i++) if( d >> i & 1 ) x = parent[i][x]; if( x == y ) return x; for(int i = logn-1 ; i >= 0 ; i--){ if( parent[i][x] != parent[i][y] ){ x = parent[i][x]; y = parent[i][y]; } } return parent[0][x]; } int distance(int x,int y){ return depth[x] + depth[y] - 2 * depth[lca(x,y)]; } private: int gen_lca(){ for(int i = 1 ; i < logn ; i++){ for(int j = 0 ; j < n ; j++) if( parent[i-1][j] != -1 ) parent[i][j] = parent[i-1][parent[i-1][j]]; } } int dfs(const vector> &g){ stack< array > S; S.push(array{root,-1,0}); while( S.size() ){ int x = S.top()[0]; int p = S.top()[1]; int d = S.top()[2]; S.pop(); parent[0][x] = p; depth[x] = d; for( auto e : g[x] ){ if( e != p ){ S.push(array{e,x,d+1}); child[x].push_back(e); } } } } }; mInt dp[2010][2010]; int sub[2010]; Tree tr; int subtree(int x){ if( sub[x] != 0 ) return sub[x]; for(auto c : tr.child[x] ){ sub[x] += subtree(c); } return sub[x] += 1; } int dfs(int x){ dp[x][0] = 1; for(auto c : tr.child[x] ){ dfs(c); mInt dp2[2010]; for(int k = 0 ; k <= 2000 ; k++){ if( dp[c][k].v > 0 ){ for(int j = 2000 ; j >= k ; j--){ dp2[j] += dp[c][k] * dp[x][j-k]; } } } for(int k = 0 ; k <= 2000 ; k++){ dp[x][k] = dp2[k]; //if( k == 6 ) cout << dp[x][k] << "<" << x << endl; } } dp[x][subtree(x)] += 1; } signed main(){ int N,K; cin >> N >> K; vector< pair > es; for(int i = 0 ; i+1 < N ; i++){ int a,b; cin >> a >> b; es.push_back({a,b}); } tr = Tree(N,es,0); dfs(0); cout << dp[0][K] << endl; }