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;
struct node {
  int t, next;
} a[200010];
long long DCXISSOHANDSOME[20][262144], inv[262145], fac[100010], ifac[100010],
    f[100010], g[100010], ans;
int head[100010], size[100010], h[100010], n, k, tt, tot;
inline int rd() {
  int x = 0;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    ;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  return x;
}
inline void add(int x, int y) {
  a[++tot].t = y;
  a[tot].next = head[x];
  head[x] = tot;
}
inline long long pls(const long long x, const long long y) {
  return (x + y < 998244353LL) ? x + y : x + y - 998244353LL;
}
inline long long mns(const long long x, const long long y) {
  return (x - y < 0) ? x - y + 998244353LL : x - y;
}
inline long long ksm(long long x, long long y) {
  long long res = 1;
  for (; y; y >>= 1, x = x * x % 998244353LL)
    if (y & 1) res = res * x % 998244353LL;
  return res;
}
inline void pre_gao() {
  fac[0] = 1;
  for (int i = 1; i <= 100000; i++) fac[i] = fac[i - 1] * i % 998244353LL;
  ifac[100000] = ksm(fac[100000], 998244353LL - 2);
  for (int i = 99999; ~i; i--) ifac[i] = ifac[i + 1] * (i + 1) % 998244353LL;
  inv[1] = 1;
  for (int i = 2; i <= 262144; i++)
    inv[i] =
        (998244353LL - 998244353LL / i) * inv[998244353LL % i] % 998244353LL;
  for (int w = 2, hh = 1; w <= 262144; w <<= 1, hh++) {
    long long now = ksm(3, (998244353LL - 1) / w);
    DCXISSOHANDSOME[hh][0] = 1;
    for (int j = 1; j < (w >> 1); j++)
      DCXISSOHANDSOME[hh][j] = DCXISSOHANDSOME[hh][j - 1] * now % 998244353LL;
  }
}
inline void ntt(long long *a, int n, int on) {
  static int rev[262144];
  for (int i = 1; i < n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
  for (int i = 1; i < n; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int w = 2, hh = 1; w <= n; w <<= 1, hh++)
    for (int k = 0; k < n; k += w)
      for (int j = k; j < k + (w >> 1); j++) {
        long long u = a[j], t = a[j + (w >> 1)] * DCXISSOHANDSOME[hh][j - k] %
                                998244353LL;
        a[j] = pls(u, t);
        a[j + (w >> 1)] = mns(u, t);
      }
  if (on == -1) {
    reverse(a + 1, a + n);
    for (int i = 0; i < n; i++) a[i] = a[i] * inv[n] % 998244353LL;
  }
}
inline long long *gao(int l, int r) {
  static long long c[262144], d[262144];
  long long *res = new long long[r - l + 2];
  if (l == r) {
    res[0] = 1;
    res[1] = h[l];
    return res;
  }
  int mid = (l + r) >> 1;
  long long *h1 = gao(l, mid), *h2 = gao(mid + 1, r);
  int len1 = mid - l + 1, len2 = r - mid;
  int len = 1;
  for (; len <= len1 + len2; len <<= 1)
    ;
  memcpy(c, h1, sizeof(long long) * (len1 + 1));
  memcpy(d, h2, sizeof(long long) * (len2 + 1));
  memset(c + len1 + 1, 0, sizeof(long long) * (len - len1 - 1));
  memset(d + len2 + 1, 0, sizeof(long long) * (len - len2 - 1));
  ntt(c, len, 1);
  ntt(d, len, 1);
  for (int i = 0; i < len; i++) c[i] = c[i] * d[i] % 998244353LL;
  ntt(c, len, -1);
  memcpy(res, c, sizeof(long long) * (r - l + 2));
  delete[] h1;
  delete[] h2;
  return res;
}
inline void dfs(int x, int y) {
  static long long c[262144], d[262144];
  g[x] = 0;
  size[x] = 1;
  for (int i = head[x]; i; i = a[i].next) {
    int t = a[i].t;
    if (t == y) continue;
    dfs(t, x);
    size[x] += size[t];
    ans = pls(ans, g[x] * g[t] % 998244353LL);
    g[x] = pls(g[x], g[t]);
  }
  tt = 0;
  for (int i = head[x]; i; i = a[i].next)
    if (a[i].t != y) h[++tt] = size[a[i].t];
  if (!tt) {
    f[x] = g[x] = 1;
    return;
  }
  long long *res = gao(1, tt);
  for (int i = 0; i <= min(k, tt); i++)
    f[x] = pls(f[x], res[i] * fac[k] % 998244353LL * ifac[k - i] % 998244353LL);
  g[x] = pls(g[x], f[x]);
  int m = tt;
  sort(h + 1, h + m + 1);
  m = unique(h + 1, h + m + 1) - h - 1;
  for (int i = tt; i; i--)
    c[i] = pls(res[i - 1] * (n - size[x]) % 998244353LL, res[i]);
  c[0] = res[0];
  for (int hhh = 1; hhh <= m; hhh++) {
    d[0] = 1;
    for (int i = 1; i <= tt; i++)
      d[i] = mns(c[i], d[i - 1] * h[hhh] % 998244353LL);
    long long now = 0;
    for (int i = 0; i <= min(k, tt); i++)
      now = pls(now, d[i] * fac[k] % 998244353LL * ifac[k - i] % 998244353LL);
    for (int i = head[x]; i; i = a[i].next)
      if (a[i].t != y && size[a[i].t] == h[hhh])
        ans = pls(ans, g[a[i].t] * now % 998244353LL);
  }
}
int main() {
  n = rd();
  k = rd();
  pre_gao();
  tot = 0;
  if (k == 1) {
    printf("%I64d\n", (long long)n * (n - 1) / 2 % 998244353LL);
    return 0;
  }
  for (int i = 1; i < n; i++) {
    int x = rd(), y = rd();
    add(x, y);
    add(y, x);
  }
  ans = 0;
  dfs(1, 0);
  printf("%I64d\n", ans);
  return 0;
}