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 std::lower_bound;
using std::max;
using std::min;
using std::random_shuffle;
using std::reverse;
using std::sort;
using std::swap;
using std::unique;
using std::upper_bound;
using std::vector;
void open(const char *s) {}
int rd() {
  int s = 0, c, b = 0;
  while (((c = getchar()) < '0' || c > '9') && c != '-')
    ;
  if (c == '-') {
    c = getchar();
    b = 1;
  }
  do {
    s = s * 10 + c - '0';
  } while ((c = getchar()) >= '0' && c <= '9');
  return b ? -s : s;
}
void put(int x) {
  if (!x) {
    putchar('0');
    return;
  }
  static int c[20];
  int t = 0;
  while (x) {
    c[++t] = x % 10;
    x /= 10;
  }
  while (t) putchar(c[t--] + '0');
}
int upmin(int &a, int b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
int upmax(int &a, int b) {
  if (b > a) {
    a = b;
    return 1;
  }
  return 0;
}
const long long p = 998244353;
const int N = 100010;
long long fp(long long a, long long b) {
  long long s = 1;
  for (; b; b >>= 1, a = a * a % p)
    if (b & 1) s = s * a % p;
  return s;
}
namespace ntt {
const int N = 300000;
const int W = 1 << 18;
long long plus(long long a, long long b) {
  a += b;
  return a >= p ? a - p : a;
}
long long minus(long long a, long long b) {
  a -= b;
  return a >= 0 ? a : a + p;
}
long long w[N];
int rev[N];
void ntt(long long *a, int n, int t) {
  for (int i = 1; i < n; i++) {
    rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? n >> 1 : 0);
    if (rev[i] > i) swap(a[i], a[rev[i]]);
  }
  for (int i = 0; i < n; i++) a[i] = plus(a[i], p);
  for (int i = 2; i <= n; i <<= 1)
    for (int j = 0; j < n; j += i)
      for (int k = 0; k < i / 2; k++) {
        long long u = a[j + k];
        long long v = a[j + k + i / 2] * w[W / i * k] % p;
        a[j + k] = plus(u, v);
        a[j + k + i / 2] = minus(u, v);
      }
  if (t == -1) {
    reverse(a + 1, a + n);
    long long inv = fp(n, p - 2);
    for (int i = 0; i < n; i++) a[i] = a[i] * inv % p;
  }
}
void init() {
  long long s = fp(3, (p - 1) / W);
  w[0] = 1;
  for (int i = 1; i < W / 2; i++) w[i] = w[i - 1] * s % p;
}
void mul(long long *a, long long *b, long long *c, int n, int m, int l) {
  static long long a1[N], a2[N];
  int k = 1;
  while (k <= n + m) k <<= 1;
  for (int i = 0; i < k; i++) a1[i] = a2[i] = 0;
  for (int i = 0; i <= n; i++) a1[i] = a[i];
  for (int i = 0; i <= m; i++) a2[i] = b[i];
  ntt(a1, k, 1);
  ntt(a2, k, 1);
  for (int i = 0; i < k; i++) a1[i] = a1[i] * a2[i] % p;
  ntt(a1, k, -1);
  for (int i = 0; i <= l; i++) c[i] = a1[i];
}
void mul2(long long *a, long long *b, long long *c, long long *d, long long *e,
          int n, int m, int l) {
  static long long a1[N], a2[N], a3[N], a4[N];
  int k = 1;
  while (k <= n + m) k <<= 1;
  for (int i = 0; i < k; i++) a1[i] = a2[i] = a3[i] = a4[i] = 0;
  for (int i = 0; i <= n; i++) {
    a1[i] = a[i];
    a3[i] = c[i];
  }
  for (int i = 0; i <= m; i++) {
    a2[i] = b[i];
    a4[i] = d[i];
  }
  ntt(a1, k, 1);
  ntt(a2, k, 1);
  ntt(a3, k, 1);
  ntt(a4, k, 1);
  for (int i = 0; i < k; i++) a1[i] = a1[i] * a2[i] % p;
  for (int i = 0; i < k; i++) a3[i] = a3[i] * a4[i] % p;
  ntt(a1, k, -1);
  ntt(a3, k, -1);
  for (int i = 0; i <= l; i++) e[i] = (a1[i] + a3[i]) % p;
}
}  // namespace ntt
vector<int> g[N];
int s[N];
int n, k;
long long ans = 0;
long long fac[N];
long long ifac[N];
void init() {
  fac[0] = 1;
  for (int i = 1; i <= k; i++) fac[i] = fac[i - 1] * i % p;
  ifac[k] = fp(fac[k], p - 2);
  for (int i = k; i >= 1; i--) ifac[i - 1] = ifac[i] * i % p;
}
long long binom(int x, int y) {
  return x >= y && y >= 0 ? fac[x] * ifac[y] % p * ifac[x - y] % p : 0;
}
long long f1[N];
long long f2[N];
long long c[N];
long long d[N];
int l;
typedef std::pair<long long *, long long *> _;
_ solve(int l, int r) {
  _ s;
  if (l == r) {
    s.first = new long long[2];
    s.second = new long long[2];
    s.first[0] = 1;
    s.first[1] = c[l];
    s.second[0] = d[l];
    s.second[1] = d[l] * c[0] % p;
    return s;
  }
  int mid = (l + r) >> 1;
  _ ls = solve(l, mid);
  _ rs = solve(mid + 1, r);
  s.first = new long long[r - l + 2];
  s.second = new long long[r - l + 2];
  ntt::mul(ls.first, rs.first, s.first, mid - l + 1, r - mid, r - l + 1);
  ntt::mul2(ls.second, rs.first, ls.first, rs.second, s.second, mid - l + 1,
            r - mid, r - l + 1);
  return s;
}
void dfs(int x, int fa) {
  s[x] = 1;
  for (auto v : g[x])
    if (v != fa) {
      dfs(v, x);
      s[x] += s[v];
      ans = (ans + f2[x] * f2[v]) % p;
      f2[x] = (f2[x] + f2[v]) % p;
    }
  if (s[x] == 1) {
    f1[x] = f2[x] = 1;
    return;
  }
  l = 0;
  for (auto v : g[x])
    if (v != fa) {
      c[++l] = s[v];
      d[l] = f2[v];
    }
  c[0] = n - s[x];
  _ e = solve(1, l);
  for (int i = 0; i <= l && i <= k; i++) {
    f1[x] = (f1[x] + e.first[i] * binom(k, i) % p * fac[i]) % p;
    ans = (ans + e.second[i] * binom(k, i) % p * fac[i]) % p;
  }
  f2[x] = (f2[x] + f1[x]) % p;
}
int main() {
  ntt::init();
  open("cf981h");
  scanf("%d%d", &n, &k);
  if (k == 1) {
    printf("%I64d\n", (long long)n * (n - 1) / 2 % p);
    return 0;
  }
  init();
  int x, y;
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1, 0);
  printf("%I64d\n", ans);
  return 0;
}