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;
template <typename T>
inline bool cmax(T &x, T y) {
  return y > x ? x = y, true : false;
}
template <typename T>
inline bool cmin(T &x, T y) {
  return y < x ? x = y, true : false;
}
template <typename T>
inline T dmax(T x, T y) {
  return x > y ? x : y;
}
template <typename T>
inline T dmin(T x, T y) {
  return x < y ? x : y;
}
const int mod = 998244353;
const int MAXN = 4e5 + 5;
const int oo = 0x3f3f3f3f;
const int L = 3e5;
inline int add(int a, int b) {
  a += b;
  return a >= mod ? a - mod : a;
}
inline int pop(int a, int b) {
  a -= b;
  return a < 0 ? a + mod : a;
}
inline int mul(int a, int b) { return (long long)a * b % mod; }
int qpow(int a, int b) {
  int c = 1;
  while (b) {
    if (b & 1) c = mul(c, a);
    a = mul(a, a);
    b >>= 1;
  }
  return c;
}
int omega[MAXN], inv[MAXN], A[MAXN], B[MAXN], pos[MAXN], ans = 0;
int fac[MAXN], invfac[MAXN];
inline int C(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return mul(fac[a], mul(invfac[b], invfac[a - b]));
}
int init(int N) {
  int n = 1;
  while (n < N) n <<= 1;
  for (int i = 0; i <= n - 1; i++) {
    pos[i] = pos[i >> 1] >> 1;
    if (i & 1) pos[i] |= n >> 1;
  }
  omega[0] = inv[0] = 1;
  int x = qpow(3, (mod - 1) / n), y = qpow(x, mod - 2);
  for (int i = 1; i <= n - 1; i++) {
    omega[i] = mul(omega[i - 1], x);
    inv[i] = mul(inv[i - 1], y);
  }
  return n;
}
void FFT(int n, int *a, bool idft) {
  for (int i = 0; i <= n - 1; i++)
    if (pos[i] < i) swap(a[pos[i]], a[i]);
  int *w = idft ? inv : omega;
  for (int len = 2; len <= n; len <<= 1) {
    int m = len >> 1;
    for (int j = 0; j < n; j += len)
      for (int k = 0; k <= m - 1; k++) {
        int z = mul(a[j + m + k], w[n / len * k]);
        a[j + m + k] = pop(a[j + k], z);
        a[j + k] = add(a[j + k], z);
      }
  }
  if (idft) {
    int x = qpow(n, mod - 2);
    for (int i = 0; i <= n - 1; i++) a[i] = mul(a[i], x);
  }
}
int N, K, dfn[MAXN], rev[MAXN], ord, siz[MAXN], suf[MAXN];
int f[MAXN], sz[MAXN], m, w[21][MAXN], w1[21][MAXN], all[21];
int g[MAXN], _w[MAXN];
pair<int, int> Work(int le, int ri, int dep) {
  if (le == ri) {
    int cl = all[dep] + 1, cr = cl + 1;
    w[dep][cl] = 1;
    w[dep][cr] = sz[le];
    all[dep] = cr;
    return make_pair(cl, cr);
  }
  int mi = (le + ri) >> 1, cl = all[dep] + 1, cr = cl + ri - le + 1;
  all[dep] = cr;
  pair<int, int> p = Work(le, mi, dep + 1), q = Work(mi + 1, ri, dep + 1);
  int n = init(ri - le + 2);
  memset(A, 0, sizeof(int) * n);
  memset(B, 0, sizeof(int) * n);
  for (int i = p.first; i <= p.second; i++) A[i - p.first] = w[dep + 1][i];
  for (int i = q.first; i <= q.second; i++) B[i - q.first] = w[dep + 1][i];
  FFT(n, A, 0);
  FFT(n, B, 0);
  for (int i = 0; i <= n - 1; i++) A[i] = mul(A[i], B[i]);
  FFT(n, A, 1);
  for (int i = cl; i <= cr; i++) w[dep][i] = A[i - cl];
  return make_pair(cl, cr);
}
pair<int, int> re_Work(int le, int ri, int dep) {
  if (le == ri) {
    int cl = all[dep] + 1, cr = cl + 1;
    w[dep][cl] = 1;
    w[dep][cr] = sz[le];
    w1[dep][cl] = _w[le];
    w1[dep][cr] = 0;
    all[dep] = cr;
    return make_pair(cl, cr);
  }
  int mi = (le + ri) >> 1, cl = all[dep] + 1, cr = cl + ri - le + 1;
  all[dep] = cr;
  pair<int, int> p = re_Work(le, mi, dep + 1), q = re_Work(mi + 1, ri, dep + 1);
  int n = init(ri - le + 2);
  for (int i = cl; i <= cr; i++) w[dep][i] = w1[dep][i] = 0;
  int *ss[2] = {w[dep + 1], w1[dep + 1]};
  int *tt[2] = {w[dep], w1[dep]};
  for (int x = 0; x <= 1; x++)
    for (int y = 0; y <= 1; y++)
      if (x + y < 2) {
        memset(A, 0, sizeof(int) * n);
        memset(B, 0, sizeof(int) * n);
        for (int i = p.first; i <= p.second; i++) A[i - p.first] = ss[x][i];
        for (int i = q.first; i <= q.second; i++) B[i - q.first] = ss[y][i];
        FFT(n, A, 0);
        FFT(n, B, 0);
        for (int i = 0; i <= n - 1; i++) A[i] = mul(A[i], B[i]);
        FFT(n, A, 1);
        for (int i = cl; i <= cr; i++)
          tt[x + y][i] = add(tt[x + y][i], A[i - cl]);
      }
  return make_pair(cl, cr);
}
int calc() {
  if (m == 0) return 1;
  for (int i = 0; i <= 20; i++) all[i] = 0;
  pair<int, int> ww = Work(1, m, 0);
  int cl = ww.first, cr = ww.second, sum = 0;
  cmin(cr, cl + K);
  for (int i = cl; i <= cr; i++)
    sum = add(sum, mul(mul(w[0][i], fac[i - cl]), C(K, K - (i - cl))));
  return sum;
}
struct edge {
  int y, next;
} e[MAXN << 1];
int LINK[MAXN], len = 0;
inline void ins(int x, int y) {
  e[++len].next = LINK[x];
  LINK[x] = len;
  e[len].y = y;
}
inline void Ins(int x, int y) {
  ins(x, y);
  ins(y, x);
}
void DFS(int node, int fa) {
  dfn[node] = ++ord;
  rev[ord] = node;
  siz[node] = 1;
  for (int i = LINK[node]; i; i = e[i].next)
    if (e[i].y != fa) {
      DFS(e[i].y, node);
      siz[node] += siz[e[i].y];
    }
  m = 0;
  for (int i = LINK[node]; i; i = e[i].next)
    if (e[i].y != fa) sz[++m] = siz[e[i].y];
  f[node] = calc();
}
void reDFS(int node, int fa) {
  int son = 0;
  g[node] = f[node];
  for (int i = LINK[node]; i; i = e[i].next)
    if (e[i].y != fa) {
      reDFS(e[i].y, node);
      g[node] = add(g[node], g[e[i].y]);
      son++;
    }
  m = 0;
  for (int i = LINK[node]; i; i = e[i].next)
    if (e[i].y != fa) {
      sz[++m] = siz[e[i].y];
      _w[m] = g[e[i].y];
    }
  if (fa) {
    sz[++m] = N - siz[node], son++;
    _w[m] = 0;
  }
  if (m) {
    for (int i = 0; i <= 20; i++) all[i] = 0;
    pair<int, int> ww = re_Work(1, m, 0);
    int cl = ww.first, cr = ww.second;
    cmin(cr, cl + K);
    for (int i = cl; i <= cr; i++)
      ans = add(ans, mul(w1[0][i], mul(C(K, K - (i - cl)), fac[i - cl])));
  }
}
int main() {
  scanf("%d%d", &N, &K);
  if (K == 1) return 0 * printf("%lld\n", ((long long)N * (N - 1) / 2) % mod);
  fac[0] = invfac[0] = invfac[1] = 1;
  for (int i = 2; i <= L; i++) invfac[i] = mul(mod - mod / i, invfac[mod % i]);
  for (int i = 1; i <= L; i++) fac[i] = mul(i, fac[i - 1]);
  for (int i = 1; i <= L; i++) invfac[i] = mul(invfac[i], invfac[i - 1]);
  for (int i = 2; i <= N; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    Ins(x, y);
  }
  DFS(1, 0);
  for (int i = N; i >= 1; i--) {
    ans = add(ans, mul(f[rev[i]], suf[i + siz[rev[i]]]));
    suf[i] = add(suf[i + 1], f[rev[i]]);
  }
  reDFS(1, 0);
  printf("%d\n", ans);
  return 0;
}