Problem: You are given a tree of n vertices. You are to select k (not necessarily distinct) simple paths in such a way that it is possible to split all edges of the tree into three sets: edges not contained in any path, edges that are a part of exactly one of these paths, and edges that are parts of all selected paths, and the latter set should be non-empty.

Compute the number of ways to select k paths modulo 998244353.

The paths are enumerated, in other words, two ways are considered distinct if there are such i (1 ≤ i ≤ k) and an edge that the i-th path contains the edge in one way and does not contain it in the other.

Input

The first line contains two integers n and k (1 ≤ n, k ≤ 10^{5}) — the number of vertices in the tree and the desired number of paths.

The next n - 1 lines describe edges of the tree. Each line contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b) — the endpoints of an edge. It is guaranteed that the given edges form a tree.

Output

Print the number of ways to select k enumerated not necessarily distinct simple paths in such a way that for each edge either it is not contained in any path, or it is contained in exactly one path, or it is contained in all k paths, and the intersection of all paths is non-empty. 

As the answer can be large, print it modulo 998244353.

Examples

Input

3 2
1 2
2 3


Output

7


Input

5 1
4 1
2 3
4 5
2 1


Output

10


Input

29 29
1 2
1 3
1 4
1 5
5 6
5 7
5 8
8 9
8 10
8 11
11 12
11 13
11 14
14 15
14 16
14 17
17 18
17 19
17 20
20 21
20 22
20 23
23 24
23 25
23 26
26 27
26 28
26 29


Output

125580756

Note

In the first example the following ways are valid：

  * ((1,2), (1,2)), 
  * ((1,2), (1,3)), 
  * ((1,3), (1,2)), 
  * ((1,3), (1,3)), 
  * ((1,3), (2,3)), 
  * ((2,3), (1,3)), 
  * ((2,3), (2,3)). 



In the second example k=1, so all n ⋅ (n - 1) / 2 = 5 ⋅ 4 / 2 = 10 paths are valid.

In the third example, the answer is ≥ 998244353, so it was taken modulo 998244353, don't forget it!

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
inline void add(int &x, int y) {
  int t = x + y;
  if (t >= mod) t -= mod;
  x = t;
}
inline void sub(int &x, int y) {
  int t = x - y + mod;
  if (t >= mod) t -= mod;
  x = t;
}
inline int inc(int x, int y) {
  int t = x + y;
  return t >= mod ? t - mod : t;
}
inline int mul(int x, int y) { return (long long)x * y % mod; }
inline int power(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) {
      res = mul(res, x);
    }
    x = mul(x, x);
    y >>= 1;
  }
  return res;
}
inline int inv(int a) {
  int b = mod, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  if (u < 0) {
    u += mod;
  }
  return u;
}
namespace ntt {
int base = 1, root = -1, max_base = -1;
vector<int> rev = {0, 1}, roots = {0, 1};
void init() {
  int temp = mod - 1;
  max_base = 0;
  while (temp % 2 == 0) {
    temp >>= 1;
    ++max_base;
  }
  root = 2;
  while (true) {
    if (power(root, 1 << max_base) == 1 &&
        power(root, 1 << (max_base - 1)) != 1) {
      break;
    }
    ++root;
  }
}
void ensure_base(int nbase) {
  if (max_base == -1) {
    init();
  }
  if (nbase <= base) {
    return;
  }
  assert(nbase <= max_base);
  rev.resize(1 << nbase);
  for (int i = 0; i < 1 << nbase; ++i) {
    rev[i] = rev[i >> 1] >> 1 | (i & 1) << (nbase - 1);
  }
  roots.resize(1 << nbase);
  while (base < nbase) {
    int z = power(root, 1 << (max_base - 1 - base));
    for (int i = 1 << (base - 1); i < 1 << base; ++i) {
      roots[i << 1] = roots[i];
      roots[i << 1 | 1] = mul(roots[i], z);
    }
    ++base;
  }
}
void dft(vector<int> &a) {
  int n = (int)a.size(), zeros = __builtin_ctz(n);
  ensure_base(zeros);
  int shift = base - zeros;
  for (int i = 0; i < n; ++i) {
    if (i < rev[i] >> shift) {
      swap(a[i], a[rev[i] >> shift]);
    }
  }
  for (int i = 1; i < n; i <<= 1) {
    for (int j = 0; j < n; j += i << 1) {
      for (int k = 0; k < i; ++k) {
        int x = a[j + k], y = mul(a[j + k + i], roots[i + k]);
        a[j + k] = (x + y) % mod;
        a[j + k + i] = (x + mod - y) % mod;
      }
    }
  }
}
vector<int> multiply(vector<int> a, vector<int> b) {
  int need = (int)a.size() + (int)b.size() - 1, nbase = 0;
  while (1 << nbase < need) {
    ++nbase;
  }
  ensure_base(nbase);
  int sz = 1 << nbase;
  a.resize(sz);
  b.resize(sz);
  bool equal = a == b;
  dft(a);
  if (equal) {
    b = a;
  } else {
    dft(b);
  }
  int inv_sz = inv(sz);
  for (int i = 0; i < sz; ++i) {
    a[i] = mul(mul(a[i], b[i]), inv_sz);
  }
  reverse(a.begin() + 1, a.end());
  dft(a);
  a.resize(need);
  return a;
}
}  // namespace ntt
using ntt::multiply;
vector<int> &operator+=(vector<int> &a, const vector<int> &b) {
  if (a.size() < b.size()) {
    a.resize(b.size());
  }
  for (int i = 0; i < (int)b.size(); ++i) {
    add(a[i], b[i]);
  }
  return a;
}
vector<int> operator+(const vector<int> &a, const vector<int> &b) {
  vector<int> c = a;
  return c += b;
}
vector<int> &operator-=(vector<int> &a, const vector<int> &b) {
  if (a.size() < b.size()) {
    a.resize(b.size());
  }
  for (int i = 0; i < (int)b.size(); ++i) {
    sub(a[i], b[i]);
  }
  return a;
}
vector<int> operator-(const vector<int> &a, const vector<int> &b) {
  vector<int> c = a;
  return c -= b;
}
vector<int> &operator*=(vector<int> &a, const vector<int> &b) {
  if ((int)min(a.size(), b.size()) < 128) {
    vector<int> c = a;
    a.assign(a.size() + b.size() - 1, 0);
    for (int i = 0; i < (int)c.size(); ++i) {
      for (int j = 0; j < (int)b.size(); ++j) {
        add(a[i + j], mul(c[i], b[j]));
      }
    }
  } else {
    a = multiply(a, b);
  }
  return a;
}
vector<int> operator*(const vector<int> &a, const vector<int> &b) {
  vector<int> c = a;
  return c *= b;
}
vector<int> multiply_all(vector<vector<int>> &all, int l = -1, int r = -1) {
  if (!~l) {
    l = 0;
    r = (int)all.size() - 1;
  }
  if (l > r) {
    return vector<int>();
  } else if (l == r) {
    return all[l];
  } else {
    int y = (l + r) >> 1;
    return multiply_all(all, l, y) * multiply_all(all, y + 1, r);
  }
}
vector<int> multi(vector<int> &p, int x) {
  vector<int> q(p.size() + 1);
  for (int i = 0; i < (int)p.size(); i++) {
    add(q[i], p[i]);
    add(q[i + 1], mul(p[i], x));
  }
  return q;
}
vector<int> divi(vector<int> p, int x) {
  vector<int> q(p.size() - 1);
  int ix = inv(x);
  for (int i = (int)q.size() - 1; i >= 0; i--) {
    q[i] = mul(p[i + 1], ix);
    sub(p[i], q[i]);
  }
  return q;
}
const int N = 100030;
int n, k, size[N], f[N], g[N], answer;
vector<int> G[N];
int calc(const vector<int> &p) {
  int result = 0;
  for (int i = 0, coef = 1; i < (int)p.size(); i++) {
    add(result, mul(coef, p[i]));
    coef = mul(coef, k - i);
  }
  return result;
}
void dfs(int x, int pre) {
  size[x] = 1;
  for (auto y = G[x].begin(); y != G[x].end(); y++) {
    if (*y == pre) {
      G[x].erase(y);
      break;
    }
  }
  vector<vector<int>> all;
  for (auto y : G[x]) {
    dfs(y, x);
    size[x] += size[y];
    all.push_back(vector<int>{1, size[y]});
  }
  sort(G[x].begin(), G[x].end(),
       [&](int x, int y) { return size[x] < size[y]; });
  vector<int> p = multiply_all(all);
  if (!p.size()) {
    p = vector<int>(1, 1);
  }
  f[x] = calc(p);
  if (k == 1) f[x] = 1;
  p = multi(p, n - size[x]);
  int last_size = 0, last_ans = 0;
  for (auto y : G[x]) {
    if (size[y] == last_size) {
      g[y] = last_ans;
    } else {
      vector<int> q = divi(p, size[y]);
      last_size = size[y];
      g[y] = last_ans = calc(q);
    }
    if (k == 1) g[y] = 1;
  }
}
void dfs(int x) {
  int sum = 0;
  for (auto y : G[x]) {
    dfs(y);
    add(answer, mul(sum, f[y]));
    add(sum, f[y]);
  }
  add(f[x], sum);
  add(answer, mul(f[x], g[x]));
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1, x, y; i < n; i++) {
    scanf("%d%d", &x, &y);
    G[x].push_back(y);
    G[y].push_back(x);
  }
  dfs(1, 0);
  dfs(1);
  printf("%d\n", answer);
}