Problem: A great legend used to be here, but some troll hacked Codeforces and erased it. Too bad for us, but in the troll society he earned a title of an ultimate-greatest-over troll. At least for them, it's something good. And maybe a formal statement will be even better for us?

You are given a tree T with n vertices numbered from 1 to n. For every non-empty subset X of vertices of T, let f(X) be the minimum number of edges in the smallest connected subtree of T which contains every vertex from X.

You're also given an integer k. You need to compute the sum of (f(X))^k among all non-empty subsets of vertices, that is:

$$$ ∑_{X ⊆ \{1, 2,\: ... \:, n\},  X ≠ ∅} (f(X))^k. $$$

As the result might be very large, output it modulo 10^9 + 7.

Input

The first line contains two integers n and k (2 ≤ n ≤ 10^5, 1 ≤ k ≤ 200) — the size of the tree and the exponent in the sum above.

Each of the following n - 1 lines contains two integers a_i and b_i (1 ≤ a_i,b_i ≤ n) — the indices of the vertices connected by the corresponding edge.

It is guaranteed, that the edges form a tree.

Output

Print a single integer — the requested sum modulo 10^9 + 7.

Examples

Input


4 1
1 2
2 3
2 4


Output


21


Input


4 2
1 2
2 3
2 4


Output


45


Input


5 3
1 2
2 3
3 4
4 5


Output


780

Note

In the first two examples, the values of f are as follows:

f(\{1\}) = 0

f(\{2\}) = 0

f(\{1, 2\}) = 1

f(\{3\}) = 0

f(\{1, 3\}) = 2

f(\{2, 3\}) = 1

f(\{1, 2, 3\}) = 2

f(\{4\}) = 0

f(\{1, 4\}) = 2

f(\{2, 4\}) = 1

f(\{1, 2, 4\}) = 2

f(\{3, 4\}) = 2

f(\{1, 3, 4\}) = 3

f(\{2, 3, 4\}) = 2

f(\{1, 2, 3, 4\}) = 3

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
auto& errStream = cerr;
class CerrDummy {
} cerrDummy;
template <class T>
CerrDummy& operator<<(CerrDummy& cd, const T&) {
  return cd;
}
using charTDummy = char;
using traitsDummy = char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy& cd,
                      basic_ostream<charTDummy, traitsDummy>&(
                          basic_ostream<charTDummy, traitsDummy>&)) {
  return cd;
}
using pi = pair<ll, ll>;
using vi = vector<ll>;
using ld = long double;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (ll i = ll(0); i < ll((ll)v.size()); i++) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}
ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}
void printSpace() { printf(" "); }
void printEoln() { printf("\n"); }
void print(ll x, ll suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1) printEoln();
  if (suc == 2) printSpace();
}
string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}
char* readCharArray() {
  static char buf[3341000];
  static ll bufUsed = 0;
  char* ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}
template <class T, class U>
void chmax(T& a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
void chmin(T& a, U b) {
  if (b < a) a = b;
}
template <class T>
T Sq(const T& t) {
  return t * t;
}
void Yes(bool ex = true) {
  cout << "YES" << endl;
  if (ex) exit(0);
}
void No(bool ex = true) {
  cout << "NO" << endl;
  if (ex) exit(0);
}
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
template <ll mod>
struct ModInt {
  ll v;
  ModInt() : v(0) {}
  ModInt(ll vv) : v((vv % mod + mod) % mod) {}
  explicit operator bool() const { return v; }
  explicit operator ll() const { return v; }
  ModInt operator-() const { return ModInt(0) - *this; }
  ModInt& operator+=(const ModInt& rhs) {
    v += rhs.v;
    if (v >= mod) v -= mod;
    return *this;
  }
  ModInt& operator-=(const ModInt& rhs) {
    v -= rhs.v;
    if (v < 0) v += mod;
    return *this;
  }
  ModInt& operator*=(const ModInt& rhs) {
    v *= rhs.v;
    v %= mod;
    return *this;
  }
  ModInt& operator/=(const ModInt& rhs) {
    operator*=(rhs.inv());
    return *this;
  }
  ModInt operator+(const ModInt& rhs) const { return ModInt(*this) += rhs; }
  ModInt operator-(const ModInt& rhs) const { return ModInt(*this) -= rhs; }
  ModInt operator*(const ModInt& rhs) const { return ModInt(*this) *= rhs; }
  ModInt operator/(const ModInt& rhs) const { return ModInt(*this) /= rhs; }
  friend ModInt operator+(ll x, const ModInt& y) { return ModInt(x) + y; }
  friend ModInt operator-(ll x, const ModInt& y) { return ModInt(x) - y; }
  friend ModInt operator*(ll x, const ModInt& y) { return ModInt(x) * y; }
  friend ModInt operator/(ll x, const ModInt& y) { return ModInt(x) / y; }
  ModInt pow(ll n) const {
    ModInt res(1), x(*this);
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
  ModInt inv() const { return pow(mod - 2); }
};
template <ll mod>
ostream& operator<<(ostream& os, const ModInt<mod>& m) {
  return os << m.v;
}
template <ll mod>
void print(const ModInt<mod>& m, ll suc = 1) {
  print(m.v, suc);
}
using mint = ModInt<1000000007>;
const ll Vmax = 2000010;
mint fact[Vmax], factInv[Vmax], invs[Vmax];
void InitFact() {
  fact[0] = 1;
  for (ll i = ll(1); i < ll(Vmax); i++) {
    fact[i] = fact[i - 1] * i;
  }
  factInv[Vmax - 1] = fact[Vmax - 1].inv();
  for (ll i = Vmax - 2; i >= 0; i--) {
    factInv[i] = factInv[i + 1] * (i + 1);
  }
  for (ll i = Vmax - 1; i >= 1; i--) {
    invs[i] = factInv[i] * fact[i - 1];
  }
}
mint Choose(ll n, ll k) { return fact[n] * factInv[n - k] * factInv[k]; }
mint Binom(ll a, ll b) { return fact[a + b] * factInv[a] * factInv[b]; }
mint Catalan(ll n) {
  return Binom(n, n) - (n - 1 >= 0 ? Binom(n - 1, n + 1) : 0);
}
const ll Nmax = 100010;
const ll Kmax = 210;
ll n, k, ss[Nmax];
mint dp[Nmax][Kmax];
vi tr[Nmax];
ll dfs1(ll v, ll p) {
  ss[v] = 1;
  for (auto to : tr[v])
    if (to != p) ss[v] += dfs1(to, v);
  return ss[v];
}
mint p2[Nmax], p2inv[Nmax];
void Init() {
  for (ll i = ll(0); i < ll(Nmax); i++) {
    p2[i] = mint(2).pow(i);
    p2inv[i] = p2[i].inv();
  }
}
mint waf[Kmax];
void dfs2(ll v, ll p) {
  dp[v][0] = 1;
  ll s = 0;
  for (auto to : tr[v])
    if (to != p) {
      dfs2(to, v);
      ll z = min(k, ss[to]);
      for (ll i = s; i >= 0; i--) {
        mint w = dp[v][i];
        dp[v][i] = 0;
        for (ll j = ll(0); j < ll(z + 1); j++)
          if (i + j <= k) dp[v][i + j] += w * dp[to][j];
      }
      for (ll j = ll(1); j < ll(z + 1); j++) waf[j] -= dp[to][j];
      s += z;
      chmin(s, k);
    }
  for (ll i = ll(1); i < ll(s + 1); i++) {
    waf[i] += dp[v][i];
  }
  cerrDummy << v << " " << s << endl;
  for (ll i = ll(0); i < ll(s + 1); i++) {
    cerrDummy << i << " " << dp[v][i] << endl;
  }
  for (ll i = s; i >= 0; i--) {
    mint w;
    if (i == 0) {
      w = dp[v][i] * (p2[ss[v]] - 1) * p2inv[ss[v]];
    } else {
      w = dp[v][i];
    }
    dp[v][i + 1] += w;
    if (p != -1) {
      cerrDummy << i + 1 << " " << w << endl;
      waf[i + 1] += w * (p2[n - ss[v]] - 1) * p2inv[n - ss[v]];
    }
  }
  s++;
  chmin(s, k);
  cerrDummy << v << " " << s << endl;
  for (ll i = ll(0); i < ll(s + 1); i++) {
    cerrDummy << i << " " << dp[v][i] << endl;
  }
}
signed main() {
  InitFact();
  Init();
  n = read(), k = read();
  for (ll _ = ll(0); _ < ll(n - 1); _++) {
    ll a = read() - 1, b = read() - 1;
    tr[a].push_back(b);
    tr[b].push_back(a);
  }
  dfs1(0, -1);
  dfs2(0, -1);
  mint ans = 0;
  for (ll i = ll(1); i < ll(k + 1); i++) {
    mint w = 0;
    for (ll j = ll(0); j < ll(i); j++) {
      if (j % 2 == 0)
        w += mint(i - j).pow(k) * Choose(i, j);
      else
        w -= mint(i - j).pow(k) * Choose(i, j);
    }
    cerrDummy << i << " " << waf[i] * p2[n] << endl;
    ans += waf[i] * w;
  }
  ans *= p2[n];
  print(ans);
}