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;
const double pi = acos(-1.0);
const double eps = 1e-11;
template <class T>
inline void ckmin(T& a, T b) {
  if (b < a) a = b;
}
template <class T>
inline void ckmax(T& a, T b) {
  if (b > a) a = b;
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <typename base_type, base_type _MOD>
class IntMod {
 public:
  static const int INVERSE_CACHE_SIZE = (1 << 20);
  static base_type MOD;
  static void set_mod(base_type new_mod) { MOD = new_mod; }
  base_type n;
  IntMod(long long d = 0) { n = (d >= 0 ? d % MOD : (d % MOD + MOD) % MOD); }
  virtual ~IntMod() = default;
  IntMod operator-() const { return build(n == 0 ? 0 : MOD - n); }
  IntMod& operator+=(IntMod a) {
    n = (n >= MOD - a.n ? n - MOD + a.n : n + a.n);
    return *this;
  }
  IntMod& operator-=(IntMod a) {
    n = (n >= a.n) ? n - a.n : n - a.n + MOD;
    return *this;
  }
  IntMod& operator*=(IntMod a) {
    *this = *this * a;
    return *this;
  }
  IntMod& operator/=(IntMod a) {
    *this = *this / a;
    return *this;
  }
  static IntMod build(base_type n) {
    IntMod r;
    r.n = n;
    return r;
  }
  static base_type inverse_cache[INVERSE_CACHE_SIZE];
  static bool inverse_cache_ready;
  friend IntMod inverse(IntMod n) { return build(inverse_internal(n.n)); }
  static base_type inverse_internal(base_type n) {
    if (!inverse_cache_ready) {
      inverse_cache_ready = true;
      inverse_cache[0] = 0;
      inverse_cache[1] = 1;
      for (int n = 2; n < INVERSE_CACHE_SIZE; ++n)
        inverse_cache[n] =
            (MOD -
             (base_type)((long long)inverse_cache[MOD % n] * (MOD / n) % MOD));
    }
    return n < INVERSE_CACHE_SIZE
               ? inverse_cache[n]
               : MOD - (base_type)((long long)inverse_internal(MOD % n) *
                                   (MOD / n) % MOD);
  }
  friend bool operator==(IntMod a, IntMod b) { return a.n == b.n; }
  friend bool operator!=(IntMod a, IntMod b) { return a.n != b.n; }
  friend IntMod operator+(IntMod a, IntMod b) {
    return build(a.n >= MOD - b.n ? a.n - MOD + b.n : a.n + b.n);
  }
  friend IntMod operator-(IntMod a, IntMod b) {
    return build(a.n >= b.n ? a.n - b.n : a.n - b.n + MOD);
  }
  friend IntMod operator*(IntMod a, IntMod b) {
    return build(
        static_cast<base_type>(static_cast<long long>(a.n) * b.n % MOD));
  }
  friend IntMod operator/(IntMod a, IntMod b) { return a * inverse(b); }
  friend IntMod pow(IntMod p, long long e) {
    if (e <= 0) return IntMod(1);
    IntMod r = IntMod(1);
    while (1) {
      if (e & 1) r *= p;
      e /= 2;
      if (e)
        p = p * p;
      else
        break;
    }
    return r;
  }
};
template <typename base_type, base_type _MOD>
base_type IntMod<base_type, _MOD>::inverse_cache[INVERSE_CACHE_SIZE];
template <typename base_type, base_type _MOD>
bool IntMod<base_type, _MOD>::inverse_cache_ready;
template <typename base_type, base_type _MOD>
base_type IntMod<base_type, _MOD>::MOD = _MOD;
const int MOD = 1000000007;
using Int = IntMod<int, MOD>;
const int maxn = 200000 + 16;
int n, m;
vector<int> g[maxn];
int s[maxn];
vector<Int> f[maxn];
Int pow2[maxn];
Int permutation[maxn], permutation_inv[maxn];
vector<Int> sum;
Int choose(int n, int m) {
  if (m < 0 || m > n) return 0;
  return permutation[n] * permutation_inv[m] * permutation_inv[n - m];
}
void dfs(int p, int prev) {
  vector<int> c;
  for (int x : g[p])
    if (x != prev) {
      c.push_back(x);
      dfs(x, p);
    }
  sort(c.begin(), c.end(), [](int a, int b) { return s[a] > s[b]; });
  s[p] = 1;
  for (int x : c) s[p] += s[x];
  Int f0 = 1;
  int size = min(m, s[p]) + 1;
  vector<Int> f1(size);
  vector<Int> f2(size);
  for (int x : c) {
    Int new_f0 = f0 * pow2[s[x]];
    vector<Int> new_f1(size);
    vector<Int> new_f2(size);
    const vector<Int>& h = f[x];
    for (int i = 0; i < (((int)new_f1.size())); ++i)
      new_f1[i] += f1[i] * pow2[s[x]];
    for (int i = (1); i < (((int)h.size())); ++i)
      if (h[i].n) new_f1[i] += f0 * h[i];
    for (int i = 0; i < (((int)new_f2.size())); ++i)
      new_f2[i] += f2[i] * pow2[s[x]];
    vector<int> a(((int)h.size()));
    vector<int> b(size);
    for (int i = 0; i < (((int)h.size())); ++i) a[i] = h[i].n;
    for (int i = 0; i < (size); ++i) b[i] = (f1[i] + f2[i]).n;
    for (; ((int)a.size()) > 0 && a.back() == 0; a.pop_back())
      ;
    for (; ((int)b.size()) > 0 && b.back() == 0; b.pop_back())
      ;
    int n1 = ((int)a.size()), n2 = ((int)b.size());
    for (int i = 0; i < (size); ++i) {
      int m1 = max(0, i - (n2 - 1));
      int m2 = min(n1 - 1, i);
      long long s = 0;
      for (int j = m1; j <= m2; j++) {
        s += (long long)a[j] * b[i - j];
        if (j % 8 == 0) s %= MOD;
      }
      new_f2[i] += s;
    }
    f0 = new_f0;
    f1.swap(new_f1);
    f2.swap(new_f2);
  }
  if (prev >= 0) {
    sum[1] += (pow2[n - s[p]] - 1) * (pow2[s[p]] - 1);
    for (int x : c) {
      const vector<Int>& h = f[x];
      for (int i = (1); i < (((int)h.size())); ++i)
        if (i + 1 <= m && h[i].n)
          sum[i + 1] += h[i] * (pow2[n - s[p]] - 1) * pow2[s[p] - s[x]];
    }
    for (int i = (1); i < (size); ++i)
      if (i + 1 <= m && f2[i].n) sum[i + 1] += f2[i] * (pow2[n - s[p]] - 1) * 2;
  }
  for (int i = (1); i < (size); ++i)
    if (f2[i].n) sum[i] += f2[i] * pow2[n - s[p] + 1];
  f[p].clear();
  f[p].resize(size);
  for (int i = 0; i < (size); ++i) f[p][i] += (f1[i] + f2[i]) * 2;
  if (prev >= 0) {
    f[p][1] += pow2[s[p]] - 1;
    for (int i = (1); i < (size - 1); ++i) f[p][i + 1] += (f1[i] + f2[i]) * 2;
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  pow2[0] = permutation[0] = permutation_inv[0] = 1;
  for (int i = (1); i < (maxn); ++i) {
    pow2[i] = pow2[i - 1] * 2;
    permutation[i] = permutation[i - 1] * i;
    permutation_inv[i] = permutation_inv[i - 1] / i;
  }
  while (cin >> n >> m) {
    for (int i = 0; i < (n); ++i) g[i].clear();
    for (int i = 0; i < (n); ++i) f[i].clear();
    for (int i = 0; i < (n - 1); ++i) {
      int a, b;
      cin >> a >> b;
      --a;
      --b;
      g[a].push_back(b);
      g[b].push_back(a);
    }
    sum = vector<Int>(m + 1);
    dfs(0, -1);
    Int ret = 0;
    vector<Int> cnt(m + 1);
    cnt[0] = 1;
    for (int k = (1); k < (m + 1); ++k) {
      vector<Int> cnt2(m + 1);
      for (int i = 0; i < (m + 1); ++i)
        for (int j = (1); j < (m - i + 1); ++j)
          cnt2[i + j] += cnt[i] * permutation_inv[j];
      cnt.swap(cnt2);
      ret += sum[k] * cnt[m];
    }
    ret *= permutation[m];
    printf("%d\n", ret.n);
    break;
  }
  return 0;
}