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 maxn(4e5 + 5);
const int mod(998244353);
inline void Inc(int &x, int y) { x = x + y >= mod ? x + y - mod : x + y; }
inline void Dec(int &x, int y) { x = x - y < 0 ? x - y + mod : x - y; }
inline int Add(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline int Sub(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
inline int Pow(long long x, int y) {
  long long ret = 1;
  for (; y; y >>= 1, x = x * x % mod)
    if (y & 1) ret = ret * x % mod;
  return ret;
}
int w[2][maxn], r[maxn], l, deg;
inline void Init(int len) {
  int i, x, y;
  for (l = 0, deg = 1; deg < len; deg <<= 1) ++l;
  for (i = 0; i < deg; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
  x = Pow(3, (mod - 1) / deg), y = Pow(x, mod - 2), w[0][0] = w[1][0] = 1;
  for (i = 1; i < deg; ++i)
    w[0][i] = (long long)w[0][i - 1] * x % mod,
    w[1][i] = (long long)w[1][i - 1] * y % mod;
}
inline void DFT(int *p, int opt) {
  int i, j, k, t, wn, x, y;
  for (i = 0; i < deg; ++i)
    if (r[i] < i) swap(p[r[i]], p[i]);
  for (i = 1; i < deg; i <<= 1)
    for (t = i << 1, j = 0; j < deg; j += t)
      for (k = 0; k < i; ++k) {
        wn = w[opt == -1][deg / t * k];
        x = p[j + k], y = (long long)p[j + k + i] * wn % mod;
        p[j + k] = Add(x, y), p[j + k + i] = Sub(x, y);
      }
  if (opt == -1)
    for (i = 0, wn = Pow(deg, mod - 2); i < deg; ++i)
      p[i] = (long long)p[i] * wn % mod;
}
int val[maxn], len, tmpa[20][maxn], tmpb[20][maxn], *a, *b;
void Solve(int l, int r, int *ret, int d) {
  if (l == r) {
    ret[0] = 1, ret[1] = val[l];
    return;
  }
  int mid = (l + r) >> 1, tmp = r - l + 2, i;
  Solve(l, mid, tmpa[d], d + 1), Solve(mid + 1, r, tmpb[d], d + 1);
  a = tmpa[d], b = tmpb[d], Init(tmp), DFT(a, 1), DFT(b, 1);
  for (i = 0; i < deg; ++i) a[i] = (long long)a[i] * b[i] % mod;
  DFT(a, -1);
  for (i = 0; i < tmp; ++i) ret[i] = a[i];
  for (i = 0; i < deg; ++i) a[i] = b[i] = 0;
}
int n, k, first[maxn], cnt, size[maxn], ans, tmp[maxn], dv[maxn];
int f[maxn], fac[maxn], rec[maxn], inv[maxn], g[maxn], h[maxn];
struct Edge {
  int to, next;
} edge[maxn];
inline void AddEdge(int u, int v) {
  edge[cnt] = (Edge){v, first[u]}, first[u] = cnt++;
  edge[cnt] = (Edge){u, first[v]}, first[v] = cnt++;
}
inline int Calc(int len) {
  int i, ret = 0, r = min(len, k);
  for (i = 0; i <= r; ++i)
    Inc(ret, (long long)tmp[i] * fac[k] % mod * inv[k - i] % mod);
  return ret;
}
inline void PolyDiv(int len, int v) {
  int i, inv, invv = Pow(v, mod - 2);
  for (i = 0; i <= len; ++i) dv[i] = tmp[i], tmp[i] = 0;
  for (i = len; i; --i)
    if (dv[i]) {
      tmp[i - 1] = inv = (long long)dv[i] * invv % mod;
      Dec(dv[i], (long long)inv * invv % mod), Dec(dv[i - 1], inv);
    }
}
inline void PolyMul(int len, int v) {
  int i;
  for (i = len; i; --i) Inc(tmp[i], (long long)tmp[i - 1] * v % mod);
}
inline int Cmp(int x, int y) { return size[x] < size[y]; }
void Dfs1(int u, int ff) {
  int e, v, i, j;
  size[u] = 1;
  for (e = first[u]; ~e; e = edge[e].next)
    if ((v = edge[e].to) ^ ff) Dfs1(v, u), Inc(g[u], g[v]), size[u] += size[v];
  len = 0;
  for (e = first[u]; ~e; e = edge[e].next)
    if ((v = edge[e].to) ^ ff) val[++len] = size[v];
  if (!len)
    f[u] = 1, Inc(g[u], 1);
  else {
    Solve(1, len, tmp, 0), f[u] = Calc(len), Inc(g[u], f[u]), len = 0;
    for (e = first[u]; ~e; e = edge[e].next)
      if ((v = edge[e].to) ^ ff) val[++len] = v;
    sort(val + 1, val + len + 1, Cmp);
    for (i = 0; i <= len; ++i) rec[i] = tmp[i];
    for (i = 1; i <= len; ++i) {
      if (size[val[i]] == size[val[i - 1]])
        h[val[i]] = h[val[i - 1]];
      else {
        for (j = 0; j <= len; ++j) tmp[j] = rec[j];
        PolyDiv(len, size[val[i]]), PolyMul(len, n - size[u]);
        h[val[i]] = Calc(len);
      }
    }
  }
}
void Dfs2(int u, int ff) {
  int e, v;
  for (e = first[u]; ~e; e = edge[e].next)
    if ((v = edge[e].to) ^ ff)
      Inc(ans, (long long)Sub(h[v], f[u]) * g[v] % mod), Dfs2(v, u);
}
int main() {
  memset(first, -1, sizeof(first));
  int i, u, v, sum = 0, mx;
  scanf("%d%d", &n, &k);
  if (k == 1) return printf("%lld\n", ((long long)n * (n - 1) >> 1) % mod), 0;
  mx = max(n, k);
  for (i = 1; i < n; ++i) scanf("%d%d", &u, &v), AddEdge(u, v);
  inv[0] = inv[1] = 1;
  for (i = 2; i <= mx; ++i)
    inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
  for (i = 2; i <= mx; ++i) inv[i] = (long long)inv[i - 1] * inv[i] % mod;
  for (i = fac[0] = 1; i <= mx; ++i) fac[i] = (long long)fac[i - 1] * i % mod;
  Dfs1(1, 0), Dfs2(1, 0);
  for (i = 1; i <= n; ++i) Inc(sum, f[i]);
  sum = (long long)sum * sum % mod;
  for (i = 1; i <= n; ++i) Dec(sum, (long long)f[i] * f[i] % mod);
  sum = (long long)sum * inv[2] % mod;
  Inc(ans, sum), printf("%d\n", ans);
  return 0;
}