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, c;
  while (!isdigit(c = getchar()))
    ;
  while (x = x * 10 + c - '0', isdigit(c = getchar()))
    ;
  return x;
}
struct edge {
  int to, next;
} e[262144 << 1];
int cnt, last[262144];
inline void insert(int x, int y) {
  e[++cnt].to = y;
  e[cnt].next = last[x];
  last[x] = cnt;
}
inline int ksm(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = 1ll * res * x % 998244353;
    x = 1ll * x * x % 998244353;
    y >>= 1;
  }
  return res;
}
int c[262144];
inline void NTT(int *a, int n, int f) {
  for (int i = 0; i < n; i++)
    if (i < c[i]) swap(a[i], a[c[i]]);
  for (int i = 1; i < n; i <<= 1) {
    int wn = ksm(3, 998244353 - 1 + f * (998244353 - 1) / (i << 1));
    for (int j = 0, p = i << 1; j < n; j += p) {
      int w = 1;
      for (int k = 0; k < i; k++, w = 1ll * w * wn % 998244353) {
        int x = a[j + k], y = 1ll * w * a[j + k + i] % 998244353;
        a[j + k] = (x + y) % 998244353;
        a[j + k + i] = (x - y + 998244353) % 998244353;
      }
    }
  }
  if (f == 1) return;
  int tmp = ksm(n, 998244353 - 2);
  for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * tmp % 998244353;
}
inline vector<int> operator*(const vector<int> &p, const vector<int> &q) {
  static int a[262144], b[262144];
  int N = 1;
  for (; N < q.size() + p.size(); N <<= 1)
    ;
  for (int i = 0; i < N; i++) c[i] = (c[i >> 1] >> 1) | ((i & 1) * (N >> 1));
  for (int i = 0; i < p.size(); i++) a[i] = p[i];
  for (int i = p.size(); i < N; i++) a[i] = 0;
  for (int i = 0; i < q.size(); i++) b[i] = q[i];
  for (int i = q.size(); i < N; i++) b[i] = 0;
  NTT(a, N, 1);
  NTT(b, N, 1);
  for (int i = 0; i < N; i++) a[i] = 1ll * a[i] * b[i] % 998244353;
  NTT(a, N, -1);
  vector<int> res(p.size() + q.size() - 1);
  for (int i = 0; i < q.size() + p.size() - 1; i++) res[i] = a[i];
  return res;
}
struct node {
  int x, y;
} t[262144];
int ans;
inline bool cmp(node x, node y) { return x.x < y.x; }
inline void add(int &x, int y) {
  x += y;
  x -= x >= 998244353 ? 998244353 : 0;
}
inline vector<int> solve(int l, int r) {
  if (l == r) {
    vector<int> res(2);
    res[0] = 1;
    res[1] = t[l].x;
    return res;
  }
  int mid = (l + r) >> 1;
  return solve(l, mid) * solve(mid + 1, r);
}
int sz[262144], tot, f[262144], s[262144], n, k, fac[262144], inv[262144];
inline int calc(const vector<int> &a, int n = 0) {
  int res = 0;
  for (int i = 0; i < min(k, n ? n + 1 : (int)a.size()); i++)
    add(res, 1ll * a[i] * fac[k] % 998244353 * inv[k - i] % 998244353);
  return res;
}
inline void check(const vector<int> &a) {
  printf("%d ", a.size());
  for (int i = 0; i < a.size(); i++) printf("%d ", a[i]);
  printf("\n");
}
void dfs(int x, int fa) {
  sz[x] = 1;
  for (int j = last[x]; j; j = e[j].next) {
    int y = e[j].to;
    if (y == fa) continue;
    dfs(y, x);
    sz[x] += sz[y];
    add(s[x], s[y]);
  }
  tot = 0;
  for (int j = last[x]; j; j = e[j].next) {
    int y = e[j].to;
    if (y == fa) continue;
    t[++tot].x = sz[y];
    t[tot].y = s[y];
  }
  if (!tot) {
    f[x] = s[x] = 1;
    return;
  }
  sort(t + 1, t + tot + 1, cmp);
  vector<int> res = solve(1, tot), b = res;
  f[x] = calc(res);
  add(s[x], f[x]);
  b.push_back(0);
  res.push_back(0);
  for (int i = res.size() - 1; i >= 1; i--)
    add(res[i], 1ll * res[i - 1] * (n - sz[x]) % 998244353);
  int w = 0;
  for (int i = 1; i <= tot; i++) {
    if (t[i].x == t[i - 1].x) {
      add(ans, 1ll * w * t[i].y % 998244353);
      continue;
    }
    for (int j = 0; j <= tot + 1; j++) b[j] = res[j];
    for (int j = 1; j <= tot + 1; j++)
      add(b[j], 998244353 - 1ll * b[j - 1] * t[i].x % 998244353);
    w = calc(b, tot);
    add(ans, 1ll * w * t[i].y % 998244353);
  }
}
void Dfs(int x, int fa) {
  int w = 0;
  for (int j = last[x]; j; j = e[j].next) {
    int y = e[j].to;
    if (y == fa) continue;
    Dfs(y, x);
    add(ans, 1ll * w * s[y] % 998244353);
    add(w, s[y]);
  }
}
int main() {
  n = read();
  k = read();
  fac[0] = 1;
  for (int i = 1; i <= k; i++) fac[i] = 1ll * fac[i - 1] * i % 998244353;
  inv[k] = ksm(fac[k], 998244353 - 2);
  for (int i = k; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % 998244353;
  for (int i = 1; i < n; i++) {
    int x = read(), y = read();
    insert(x, y);
    insert(y, x);
  }
  dfs(1, 0);
  Dfs(1, 0);
  printf("%d\n", ans);
  return 0;
}