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 gi() {
  int data = 0, m = 1;
  char ch = 0;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') {
    m = 0;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    data = (data << 1) + (data << 3) + (ch ^ 48);
    ch = getchar();
  }
  return (m) ? data : -data;
}
int Fac[262144], IFac[262144], inv[262144], rev[262144], f1[262144], f2[262144],
    wn[30], sz[262144], f[262144], g[262144], h[262144], Ans;
vector<int> poly[262144 << 1], vec[262144], son[262144];
int n, m, nn, K;
struct _Edge {
  int to, next;
} Edge[262144 << 1];
int head[262144], CNT;
int pson[262144], coef[262144];
inline void AddEdge(int u, int v) {
  Edge[++CNT] = (_Edge){v, head[u]};
  head[u] = CNT;
  return;
}
inline int Pow(int ts, int js) {
  int al = 1;
  while (js) {
    if (js & 1) al = 1ll * al * ts % 998244353;
    ts = 1ll * ts * ts % 998244353;
    js >>= 1;
  }
  return al;
}
inline void Numb(int N) {
  for (int i = 0; i <= 25; i++) wn[i] = Pow(3, (998244353 - 1) / (1 << i));
  Fac[0] = Fac[1] = IFac[0] = IFac[1] = inv[0] = inv[1] = 1;
  for (int i = 2; i <= N; i++) {
    Fac[i] = 1ll * i * Fac[i - 1] % 998244353;
    inv[i] = 1ll * inv[998244353 % i] * (998244353 - 998244353 / i) % 998244353;
    IFac[i] = 1ll * inv[i] * IFac[i - 1] % 998244353;
  }
  return;
}
inline int Comb(int N, int M) {
  if (N < M) return 0;
  return 1ll * Fac[N] * IFac[M] % 998244353 * IFac[N - M] % 998244353;
}
inline void NTT(int *P, int op) {
  for (int i = 0; i < nn; i++)
    if (rev[i] > i) swap(P[i], P[rev[i]]);
  for (int i = 1, id = 0; i < nn; i <<= 1) {
    ++id;
    for (int j = 0, dt = (i << 1); j < nn; j += dt) {
      int w = 1;
      for (int k = 0; k < i; k++, w = 1ll * w * wn[id] % 998244353) {
        int X = P[j + k], Y = 1ll * w * P[j + k + i] % 998244353;
        P[j + k] = (X + Y) % 998244353;
        P[j + k + i] = (X - Y + 998244353) % 998244353;
      }
    }
  }
  if (op < 0) {
    for (int j = 1; j < nn / 2; j++) swap(P[j], P[nn - j]);
    int INV = Pow(nn, 998244353 - 2);
    for (int j = 0; j < nn; j++) P[j] = 1ll * INV * P[j] % 998244353;
  }
}
int tmp[262144];
void dfs(int o, int l, int r) {
  poly[o].clear();
  if (l > r) {
    poly[o].push_back(1);
    return;
  }
  if (l == r) {
    poly[o].push_back(1), poly[o].push_back(coef[l]);
    return;
  }
  int mid = (l + r) >> 1;
  dfs(o << 1, l, mid);
  dfs(o << 1 | 1, mid + 1, r);
  int l1 = poly[o << 1].size() - 1, l2 = poly[o << 1 | 1].size() - 1;
  int nl = 0;
  for (nn = 1; nn <= l1 + l2; nn <<= 1) ++nl;
  for (int i = 0; i < nn; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (nl - 1));
  for (int i = 0; i <= l1; i++) f1[i] = poly[o << 1][i];
  for (int i = 0; i <= l2; i++) f2[i] = poly[o << 1 | 1][i];
  NTT(f1, 1);
  NTT(f2, 1);
  for (int i = 0; i < nn; i++) f1[i] = 1ll * f1[i] * f2[i] % 998244353;
  NTT(f1, -1);
  for (int i = 0; i <= l1 + l2; i++) poly[o].push_back(f1[i]);
  for (int i = 0; i < nn; i++) f1[i] = f2[i] = 0;
}
void Dfs(int u, int From) {
  sz[u] = 1;
  int sum = 0;
  for (int e = head[u]; e; e = Edge[e].next) {
    int v = Edge[e].to;
    if (v == From) continue;
    Dfs(v, u);
    sz[u] += sz[v];
    pson[u]++;
    Ans = (Ans + 1ll * f[v] * sum % 998244353) % 998244353;
    f[u] = (f[u] + f[v]) % 998244353;
    sum = (sum + f[v]) % 998244353;
  }
  int tot = 0;
  for (int e = head[u]; e; e = Edge[e].next) {
    int v = Edge[e].to;
    if (v == From) continue;
    coef[++tot] = sz[v];
  }
  dfs(1, 1, tot);
  for (int i = 0; i <= tot; i++) vec[u].push_back(poly[1][i]);
  sum = 0;
  for (int i = 0; i <= tot; i++)
    sum =
        (sum + 1ll * vec[u][i] * Fac[i] % 998244353 * Comb(K, i) % 998244353) %
        998244353;
  h[u] = sum;
  f[u] = (f[u] + sum) % 998244353;
}
inline int Calc(int u, int cof) {
  for (int i = 0; i <= pson[u]; i++) g[i] = vec[u][i];
  for (int i = 1; i <= pson[u]; i++)
    g[i] = (g[i] - 1ll * cof * g[i - 1] % 998244353 + 998244353) % 998244353;
  int sum = 0;
  for (int i = 0; i < pson[u]; i++)
    sum = (sum + 1ll * g[i] * Fac[i] % 998244353 * Comb(K, i) % 998244353) %
          998244353;
  return sum;
}
inline bool cmp(int i, int j) { return sz[i] < sz[j]; }
void Dfs2(int u, int From, int val_fa) {
  Ans = (Ans + 1ll * h[u] * val_fa % 998244353) % 998244353;
  for (int e = head[u]; e; e = Edge[e].next)
    if (Edge[e].to != From) son[u].push_back(Edge[e].to);
  sort(son[u].begin(), son[u].end(), cmp);
  if (From) {
    vec[u].push_back(0);
    ++pson[u];
    for (int j = pson[u]; j >= 1; j--)
      vec[u][j] = (1ll * vec[u][j - 1] * (n - sz[u]) % 998244353 + vec[u][j]) %
                  998244353;
  }
  int Coef = 0;
  for (int j = 0, lt = son[u].size(); j < lt; j++) {
    if (!j || sz[son[u][j]] != sz[son[u][j - 1]]) Coef = Calc(u, sz[son[u][j]]);
    int v = son[u][j];
    Dfs2(v, u, (val_fa + Coef) % 998244353);
  }
  return;
}
int main() {
  n = gi();
  K = gi();
  if (K == 1) {
    cout << (1ll * n * (n - 1) / 2) % 998244353 << endl;
    return 0;
  }
  for (int i = 1, u, v; i < n; i++)
    u = gi(), v = gi(), AddEdge(u, v), AddEdge(v, u);
  Numb(n + K);
  Dfs(1, 0);
  Dfs2(1, 0, 0);
  cout << Ans << endl;
  return 0;
}