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;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) f = ch == '-' ? -1 : f, ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * f;
}
const int P = 998244353;
inline void add(int &x, int y) { x = x + y >= P ? x + y - P : x + y; }
inline void dec(int &x, int y) { x = x < y ? x - y + P : x - y; }
inline int quick_power(int x, int y) {
  int ret = 1;
  for (; y; y >>= 1, x = 1ll * x * x % P)
    if (y & 1) ret = 1ll * ret * x % P;
  return ret;
}
const int LGL = 17;
const int L = 1 << LGL;
const int G = 3;
int poly[LGL][L];
int t[L], trs[L];
int omega[L + 5];
int len;
void NTT_pre() {
  int g = quick_power(G, (P - 1) / L);
  omega[0] = 1;
  for (int i = 1; i <= L; ++i) omega[i] = 1ll * omega[i - 1] * g % P;
}
inline void deg_pre(int deg) {
  for (len = 1; len < deg; len <<= 1)
    ;
  for (int i = 0, ret; i < len; ++i) {
    ret = 0;
    for (int x = i, j = 1; j < len; j <<= 1, x >>= 1)
      ret = (ret << 1) | (x & 1);
    trs[i] = ret;
  }
}
inline void DFT(int *a, int sig) {
  for (register int i = 0; i < len; ++i) t[trs[i]] = a[i];
  for (register int l = 2; l <= len; l <<= 1)
    for (register int h = l >> 1, j = 0,
                      wn = omega[sig > 0 ? L / l : L - L / l];
         j < len; j += l)
      for (register int i = 0, w = 1; i < h; ++i, w = 1ll * w * wn % P) {
        int u = t[i + j], v = 1ll * t[i + j + h] * w % P;
        t[i + j] = (u + v) % P, t[i + j + h] = (u - v + P) % P;
      }
  for (register int i = 0; i < len; ++i) a[i] = t[i];
  if (sig < 0)
    for (register int i = 0, inv = quick_power(len, P - 2); i < len; ++i)
      a[i] = 1ll * a[i] * inv % P;
}
inline void FFT(int *a, int *b, int *c) {
  DFT(a, 1), DFT(b, 1);
  for (register int i = 0; i < len; ++i) c[i] = 1ll * a[i] * b[i] % P;
  DFT(c, -1);
}
void solve(int *a, int l, int r, int d = 0) {
  if (l == r) {
    poly[d][0] = 1, poly[d][1] = a[l];
    return;
  }
  int mid = l + r >> 1, deg = r - l + 2, deg0 = mid - l + 2, deg1 = r - mid + 1;
  solve(a, l, mid, d + 1), copy(poly[d + 1], poly[d + 1] + deg0, poly[d]),
      solve(a, mid + 1, r, d + 1);
  deg_pre(deg), fill(poly[d] + deg0, poly[d] + len, 0),
      fill(poly[d + 1] + deg1, poly[d + 1] + len, 0);
  FFT(poly[d], poly[d + 1], poly[d]), fill(poly[d] + deg, poly[d] + len, 0);
}
const int N = 100005;
const int E = N << 1;
const int MAXK = 100005;
int last[N], deg[N], size[N], ways[N];
int fact[MAXK], invf[MAXK];
int tov[E], nxt[E];
int n, K, tot, ans;
inline void insert(int x, int y) {
  tov[++tot] = y, nxt[tot] = last[x], last[x] = tot;
}
void pre() {
  fact[0] = 1;
  for (int i = 1; i <= K; ++i) fact[i] = 1ll * fact[i - 1] * i % P;
  invf[K] = quick_power(fact[K], P - 2);
  for (int i = K; i >= 1; --i) invf[i - 1] = 1ll * invf[i] * i % P;
}
inline int C(int n, int m) {
  return n >= m ? 1ll * fact[n] * invf[m] % P * invf[n - m] % P : 0;
}
int kth[N], a[N];
inline bool cmp(int x, int y) { return size[x] < size[y]; }
inline void cancel(int *f, int x, int n) {
  for (int i = 1; i <= n; ++i) dec(f[i], 1ll * f[i - 1] * x % P);
}
inline void extend(int *f, int x, int n) {
  for (int i = n; i >= 1; --i) add(f[i], 1ll * f[i - 1] * x % P);
}
void dfs(int x, int fa = 0) {
  ways[x] = 0, size[x] = 1;
  for (int i = last[x], y; i; i = nxt[i])
    if ((y = tov[i]) != fa)
      dfs(y, x), add(ans, 1ll * ways[x] * ways[y] % P), add(ways[x], ways[y]),
          size[x] += size[y];
  for (int i = last[x]; i; i = nxt[i])
    a[deg[x]++] = tov[i] == fa ? n - size[x] : size[tov[i]];
  solve(a, 0, deg[x] - 1);
  int cnt = 0;
  for (int i = last[x], y; i; i = nxt[i])
    if ((y = tov[i]) != fa) kth[++cnt] = y;
  sort(kth + 1, kth + 1 + cnt, cmp);
  for (int i = 1, cur; i <= cnt; ++i) {
    if (i == 1 || size[kth[i]] != size[kth[i - 1]]) {
      if (i > 1) extend(poly[0], size[kth[i - 1]], deg[x]);
      cancel(poly[0], size[kth[i]], deg[x]), cur = 0;
      for (int j = 0, mul = 1; j <= deg[x]; mul = 1ll * mul * (++j) % P)
        add(cur, 1ll * poly[0][j] * C(K, j) % P * mul % P);
    }
    add(ans, 1ll * cur * ways[kth[i]] % P);
  }
  if (cnt) extend(poly[0], size[kth[cnt]], deg[x]);
  cancel(poly[0], n - size[x], deg[x]);
  for (int i = 0, mul = 1; i <= deg[x]; mul = 1ll * mul * (++i) % P)
    add(ways[x], 1ll * poly[0][i] * C(K, i) % P * mul % P);
}
int main() {
  n = read(), K = read();
  if (n > 1)
    if (K == 1)
      ans = (1ll * n * (n - 1) >> 1) % P;
    else {
      for (int i = 1, x, y; i < n; ++i)
        x = read(), y = read(), insert(x, y), insert(y, x);
      pre(), NTT_pre(), ans = 0, dfs(1);
    }
  printf("%d\n", ans);
  return 0;
}