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 N = 200010, M = 262222, mo = 998244353;
int n, K, h[N], tot, e[N], nxt[N], sz[N], cnt, d[N], vis[N], ans, g[N], son[N],
    sum, Fac[N], FInv[N], Inv[M];
int w[M], W[20][M], f[20][M], a[M], b[M], m, ti, pos[20][M], t[M];
void Add(int x, int y) {
  e[++tot] = y;
  nxt[tot] = h[x];
  h[x] = tot;
}
int quick(int x, int y) {
  int s = 1;
  for (int i = 1; i <= y; i <<= 1, x = (long long)x * x % mo)
    if (i & y) s = (long long)s * x % mo;
  return s;
}
int P(int n, int m) {
  return (n >= m && m >= 0) ? (long long)Fac[n] * FInv[m] % mo : 0;
}
void Init() {
  for (int i = 0; i < m; i++) {
    int p = 0;
    for (int j = 0, t = i; j < ti; j++, t >>= 1) p = p << 1 | (t & 1);
    pos[ti][i] = p;
  }
  W[ti][0] = 1;
  W[ti][1] = quick(3, (mo - 1) / m);
  for (int i = 2; i <= m; i++)
    W[ti][i] = (long long)W[ti][i - 1] * W[ti][1] % mo;
}
void DFT(int *a, int sig) {
  for (int i = 0; i < m; i++) t[pos[ti][i]] = a[i];
  for (int l = 2; l <= m; l <<= 1) {
    int half = l >> 1, tmp = m / l;
    for (int j = 0; j < half; j++)
      w[j] = (sig == 1) ? W[ti][j * tmp] : W[ti][m - j * tmp];
    for (int i = 0; i < m; i += l) {
      for (int j = 0; j < half; j++) {
        int p = t[i + j], q = (long long)t[i + j + half] * w[j] % mo;
        t[i + j] = (p + q >= mo) ? p + q - mo : p + q;
        t[i + j + half] = (p < q) ? p - q + mo : p - q;
      }
    }
  }
  for (int i = 0; i < m; i++)
    a[i] = (sig == 1) ? t[i] : (long long)t[i] * Inv[m] % mo;
}
void solve(int l, int r, int d) {
  if (l == r) {
    f[d][0] = 1;
    f[d][1] = sz[son[l]];
    return;
  }
  int mid = l + r >> 1;
  solve(l, mid, d + 1);
  for (int i = 0; i <= mid - l + 1; i++) f[d][i] = f[d + 1][i];
  solve(mid + 1, r, d + 1);
  for (ti = 0, m = 1; m <= 2 * (r - l + 1); m <<= 1, ti++)
    ;
  for (int i = 0; i < m; i++) a[i] = b[i] = 0;
  for (int i = 0; i <= mid - l + 1; i++) a[i] = f[d][i];
  for (int i = 0; i <= r - mid; i++) b[i] = f[d + 1][i];
  DFT(a, 1);
  DFT(b, 1);
  for (int i = 0; i < m; i++) a[i] = (long long)a[i] * b[i] % mo;
  DFT(a, -1);
  for (int i = 0; i <= r - l + 1; i++) f[d][i] = a[i];
}
bool cmp(int x, int y) { return sz[x] < sz[y]; }
void dfs(int x, int y) {
  sz[x] = 1;
  for (int i = h[x]; i; i = nxt[i])
    if (e[i] != y) {
      dfs(e[i], x);
      sz[x] += sz[e[i]];
      ans = (ans + (long long)g[x] * g[e[i]]) % mo;
      g[x] = (g[x] + g[e[i]]) % mo;
    }
  cnt = sum = 0;
  for (int i = h[x]; i; i = nxt[i])
    if (e[i] != y) {
      son[++sum] = e[i];
      if (vis[sz[e[i]]] != x) {
        vis[sz[e[i]]] = x;
        d[++cnt] = sz[e[i]];
      }
    }
  if (!sum) {
    g[x] = 1;
    return;
  }
  solve(1, sum, 0);
  for (int i = 0; i <= sum; i++)
    a[i] = f[0][i], g[x] = (g[x] + (long long)P(K, K - i) * a[i]) % mo;
  a[sum + 1] = 0;
  for (int i = sum + 1; i; i--)
    a[i] = (a[i] + (long long)a[i - 1] * (n - sz[x])) % mo;
  sort(son + 1, son + sum + 1, cmp);
  sort(d + 1, d + cnt + 1);
  for (int i = 1, j = 1; i <= cnt; i++) {
    for (int k = 0; k <= sum + 1; k++) t[k] = a[k];
    for (int k = sum + 1; k; k--) {
      int p = (long long)t[k] * Inv[d[i]] % mo;
      b[k - 1] = p;
      t[k - 1] = (t[k - 1] - p) % mo;
    }
    int s = 0;
    for (int k = 0; k <= sum; k++) s = (s + (long long)P(K, K - k) * b[k]) % mo;
    for (; j <= sum && sz[son[j]] == d[i]; j++)
      ans = (ans + (long long)g[son[j]] * s) % mo;
  }
}
int main() {
  Inv[1] = 1;
  for (int i = 2; i < M; i++)
    Inv[i] = (long long)Inv[mo % i] * (mo - mo / i) % mo;
  Fac[0] = FInv[0] = 1;
  for (int i = 1; i < N; i++) {
    Fac[i] = (long long)Fac[i - 1] * i % mo;
    FInv[i] = (long long)FInv[i - 1] * Inv[i] % mo;
  }
  scanf("%d%d", &n, &K);
  if (K == 1) {
    printf("%d\n", (long long)n * (n - 1) / 2 % mo);
    return 0;
  }
  for (int i = 1, x, y; i < n; i++) {
    scanf("%d%d", &x, &y);
    Add(x, y);
    Add(y, x);
  }
  for (ti = 0, m = 1; m < 4 * n; m <<= 1, ti++) Init();
  dfs(1, 0);
  if (ans < 0) ans += mo;
  printf("%d\n", ans);
  return 0;
}