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 N = 1e5 + 10;
const int mod = 998244353;
inline long long read() {
  long long data = 0, w = 1;
  char ch = getchar();
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') w = -1, ch = getchar();
  while (ch <= '9' && ch >= '0') data = data * 10 + ch - 48, ch = getchar();
  return data * w;
}
inline void file() {
  freopen(
      "a"
      ".in",
      "r", stdin);
}
inline void upd(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
inline void dec(int &a, int b) {
  a -= b;
  if (a < 0) a += mod;
}
inline int poww(int a, int b) {
  int res = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) res = 1ll * res * a % mod;
  return res;
}
inline void NTT(int *a, int n, int opt) {
  static int r[N << 1], l;
  for (l = 0; (1 << l) < n; l++)
    ;
  for (int i = 0; i < n; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
  for (int i = 0; i < n; i++)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int i = 2; i <= n; i <<= 1)
    for (int j = 0, wn = poww(opt == 1 ? 3 : (mod + 1) / 3, (mod - 1) / i);
         j < n; j += i)
      for (int k = j, w = 1; k < j + (i >> 1); k++, w = 1ll * w * wn % mod) {
        int x = 1ll * a[k + (i >> 1)] * w % mod;
        a[k + (i >> 1)] = (a[k] - x + mod) % mod;
        a[k] = (a[k] + x) % mod;
      }
  if (opt == -1)
    for (int i = 0, rv = poww(n, mod - 2); i < n; i++)
      a[i] = 1ll * a[i] * rv % mod;
}
inline void conv(int *f, int *g, int *h, int n, int m) {
  static int a[N << 1], b[N << 1], len;
  for (len = 1; len < n + m - 1; len <<= 1)
    ;
  for (int i = 0; i < len; i++) a[i] = b[i] = 0;
  for (int i = 0; i < n; i++) a[i] = f[i];
  for (int i = 0; i < m; i++) b[i] = g[i];
  NTT(a, len, 1);
  NTT(b, len, 1);
  for (int i = 0; i < len; i++) a[i] = 1ll * a[i] * b[i] % mod;
  NTT(a, len, -1);
  for (int i = 0; i < n + m - 1; i++) h[i] = a[i];
}
int n, k, ans;
int fac[N], inv[N], ifac[N];
inline int C(int n, int m) {
  return n < m ? 0 : 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
inline void init() {
  inv[0] = inv[1] = fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
  for (int i = 2; i <= max(n, k); i++) {
    inv[i] = mod - 1ll * (mod / i) * inv[mod % i] % mod;
    fac[i] = 1ll * i * fac[i - 1] % mod;
    ifac[i] = 1ll * inv[i] * ifac[i - 1] % mod;
  }
}
int d[N], head[N], nxt[N << 1], to[N << 1], cnt;
inline void add(int u, int v) {
  to[++cnt] = v;
  nxt[cnt] = head[u];
  head[u] = cnt;
}
int sz[N], sub[N], cov[N];
vector<int> poly[N], son[N];
inline void solve(int *f, int l, int r) {
  static int a[N], b[N];
  if (l + 1 == r) return;
  int mid = (l + r) >> 1;
  solve(f, l, mid);
  solve(f, mid, r);
  a[0] = 1;
  for (int i = l; i < mid; i++) a[i - l + 1] = f[i];
  b[0] = 1;
  for (int i = mid; i < r; i++) b[i - mid + 1] = f[i];
  conv(a, b, a, mid - l + 1, r - mid + 1);
  for (int i = l; i < r; i++) f[i] = a[i - l + 1];
}
void dfs1(int u, int ff) {
  static int f[N];
  poly[u].clear();
  poly[u].push_back(1);
  sub[u] = cov[u] = 0;
  sz[u] = 1;
  for (int i = head[u], v; i; i = nxt[i]) {
    v = to[i];
    if (v == ff) continue;
    dfs1(v, u);
    poly[u].push_back(sz[v]);
    son[u].push_back(v);
    sz[u] += sz[v];
    upd(sub[u], sub[v]);
  }
  for (int i = 1; i < d[u]; i++) f[i] = poly[u][i];
  if (d[u] > 2) solve(f, 1, d[u]);
  for (int i = 1; i < d[u]; i++) poly[u][i] = f[i];
  for (int i = 0; i < d[u]; i++)
    upd(sub[u], 1ll * fac[i] * poly[u][i] % mod * C(k, i) % mod);
}
inline bool cmp(int i, int j) { return sz[i] < sz[j]; }
void dfs2(int u, int ff) {
  static int a[N], b[N], c[N];
  a[d[u]] = 0;
  for (int i = 0; i < d[u]; i++) a[i] = poly[u][i];
  for (int i = 0; i < d[u]; i++)
    upd(a[i + 1], 1ll * (n - sz[u]) * poly[u][i] % mod);
  sort(son[u].begin(), son[u].end(), cmp);
  for (int i = 0, now = 0, v; i < d[u] - 1; i++) {
    v = son[u][i];
    if (sz[v] != now) {
      now = sz[v];
      for (int j = 0; j <= d[u]; j++) b[j] = a[j];
      for (int j = d[u]; j; j--) {
        c[j - 1] = 1ll * b[j] * inv[now] % mod;
        dec(b[j - 1], c[j - 1]);
      }
      assert(b[0] == 0);
      for (int j = 0; j < d[u]; j++)
        upd(cov[v], 1ll * c[j] * fac[j] % mod * C(k, j) % mod);
    } else
      cov[v] = cov[son[u][i - 1]];
  }
  for (int i = 0, now = 0, v, sum = 0; i < d[u] - 1; i++) {
    dfs2(v = son[u][i], u);
    upd(ans, 1ll * sum * sub[v] % mod);
    upd(sum, sub[v]);
  }
}
void dfs3(int u, int ff) {
  sz[u] = 1;
  for (int i = head[u], v; i; i = nxt[i]) {
    v = to[i];
    if (v == ff) continue;
    dfs3(v, u);
    upd(ans, 1ll * sz[u] * sz[v] % mod);
    sz[u] += sz[v];
  }
}
int main() {
  n = read();
  k = read();
  init();
  for (int i = 2, u, v; i <= n; i++) {
    u = read();
    v = read();
    d[u]++;
    d[v]++;
    add(u, v);
    add(v, u);
  }
  if (k != 1) {
    d[1]++;
    dfs1(1, 0);
    dfs2(1, 0);
    for (int u = 2; u <= n; u++) upd(ans, 1ll * sub[u] * cov[u] % mod);
  } else
    dfs3(1, 0);
  printf("%d\n", ans);
  return 0;
}