#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; const ll MOD=1e9+7; int n, k; ll dp[1010][1010]; ll s[1010][1010]; vector g[1010]; void dfs(int x, int p){ for(auto y:g[x]){ if(y==p) continue; dfs(y, x); } for(int i=1; i<=k; i++){ dp[x][i]=1; for(auto y:g[x]){ if(y==p) continue; (dp[x][i]*=s[y][i])%=MOD; } } for(int i=1; i<=k; i++){ s[x][i]=(s[x][i-1]+dp[x][i])%MOD; } } ll dp2[1010][1010]; void dfs2(int x, int p){ for(int i=1; i<=k; i++){ vector pl(1+g[x].size()), pr(1+g[x].size()); pl[0]=1; for(int j=0; j=0; j--){ int y=g[x][j]; if(y==p){ pr[j]=pr[j+1]*dp2[x][i]%MOD; }else{ pr[j]=pr[j+1]*s[y][i]%MOD; } } for(int j=0; j>n>>k; for(int i=0; i>a>>b;a--; b--; g[a].push_back(b); g[b].push_back(a); } dfs(0, -1); for(int i=1; i<=k; i++) dp2[0][i]=1; dfs2(0, -1); ll ans=0; for(int i=0; i