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 LOG = 20;
const int N = 200000 + 5;
const int r = 3, PP = 998244353;
inline int Mod(int a) {
  if (a < 0) return a + PP;
  return a >= PP ? a - PP : a;
}
inline int Mul(int a, int b) { return (long long)a * b % PP; }
inline int Pow(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = Mul(ret, a);
    a = Mul(a, a);
    b >>= 1;
  }
  return ret;
}
namespace Exp {
int n, nbit, rev[N];
void Dft(int *A, int dft) {
  for (int i = (0); i <= (int)(n - 1); ++i)
    if (i < rev[i]) swap(A[i], A[rev[i]]);
  int x, y, now, coe;
  for (int step = 1; step < n; step <<= 1) {
    coe = Pow(r, (PP - 1) / (step << 1));
    if (dft) coe = Pow(coe, PP - 2);
    for (int i = 0; i < n; i += step << 1) {
      now = 1;
      for (int j = (i); j <= (int)(i + step - 1); ++j) {
        x = A[j], y = Mul(A[j + step], now);
        A[j] = Mod(x + y);
        A[j + step] = Mod(x - y);
        now = Mul(now, coe);
      }
    }
  }
  if (dft) {
    int inv = Pow(n, PP - 2);
    for (int i = (0); i <= (int)(n - 1); ++i) A[i] = Mul(A[i], inv);
  }
}
void Mult(int *A, int *B, int n_) {
  nbit = 0;
  n = 1;
  while (n <= n_) n <<= 1, ++nbit;
  for (int i = (0); i <= (int)(n - 1); ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (nbit - 1));
  Dft(A, 0);
  Dft(B, 0);
  for (int i = (0); i <= (int)(n - 1); ++i) A[i] = Mul(A[i], B[i]), B[i] = 0;
  Dft(A, 1);
}
};  // namespace Exp
struct node {
  int o, v;
  bool operator<(const node &rhs) const { return v < rhs.v; }
} son[N];
int T[N], A[N], P[LOG][N];
int n, m, nn, fac[N], rfac[N], siz[N], val[N], f[N], sg[N];
vector<int> G[N];
void Solve(int L, int R, int o) {
  if (L == R) {
    P[o][1] = val[L];
    P[o][0] = 1;
    return;
  }
  int mid = (L + R) >> 1, len1 = mid - L + 1, len2 = R - mid;
  Solve(L, mid, o + 1);
  for (int i = (0); i <= (int)(len1); ++i)
    P[o][i] = P[o + 1][i], P[o + 1][i] = 0;
  Solve(mid + 1, R, o + 1);
  Exp::Mult(P[o], P[o + 1], R - L + 1);
  for (int i = (0); i <= (int)(len2); ++i) P[o + 1][i] = 0;
}
void Dfs_init(int u, int F) {
  siz[u] = 1;
  for (int v : G[u])
    if (v != F) Dfs_init(v, u), siz[u] += siz[v];
  int tn = 0;
  for (int v : G[u])
    if (v != F) son[++tn] = (node){v, siz[v]};
  sort(son + 1, son + tn + 1);
  for (int i = (1); i <= (int)(tn); ++i) G[u].pop_back();
  if (F) G[u].pop_back();
  G[u].push_back(F);
  for (int i = (1); i <= (int)(tn); ++i) G[u].push_back(son[i].o);
}
void Dfs(int u, int F, int sum) {
  sg[u] = sum;
  nn = 0;
  for (int v : G[u])
    if (v != F) val[++nn] = siz[v];
  if (nn)
    Solve(1, nn, 0);
  else
    P[0][0] = 1;
  for (int i = (0); i <= (int)(min(nn, m)); ++i)
    f[u] = Mod(f[u] + Mul(P[0][i], Mul(fac[m], rfac[m - i])));
  for (int i = (0); i <= (int)(nn); ++i) T[i] = P[0][i], P[0][i] = 0;
  for (int i = (nn + 1); i >= (int)(1); --i)
    T[i] = Mod(T[i] + Mul(T[i - 1], n - siz[u]));
  int v, p = 1;
  vector<int> mg;
  while (p <= nn) {
    v = G[u][p++];
    int inv = Pow(siz[v], PP - 2);
    while (p <= nn && siz[G[u][p]] == siz[v]) ++p;
    int now = T[nn + 1];
    for (int i = (nn + 1); i >= (int)(1); --i) {
      A[i - 1] = Mul(now, inv);
      now = Mod(T[i - 1] - A[i - 1]);
    }
    int av = 0;
    for (int i = (0); i <= (int)(min(nn, m)); ++i)
      av = Mod(av + Mul(A[i], Mul(fac[m], rfac[m - i])));
    mg.push_back(av);
  }
  for (int i = (0); i <= (int)(nn + 1); ++i) T[i] = A[i] = 0;
  int mn = nn, p1 = 1, p2 = 0;
  while (p1 <= mn) {
    int t = p1;
    while (t <= mn && siz[G[u][t]] == siz[G[u][p1]])
      Dfs(G[u][t], u, Mod(sum + mg[p2])), ++t;
    ++p2;
    p1 = t;
  }
}
int ans1, ans2, allf, sf[N];
void Calc(int u, int F, int sum) {
  ans2 = Mod(ans2 + Mul(f[u], sg[u]));
  sf[u] = f[u];
  for (int v : G[u])
    if (v != F) {
      Calc(v, u, Mod(sum + f[u]));
      sf[u] = Mod(sf[u] + sf[v]);
    }
  ans1 = Mod(ans1 + Mul(f[u], Mod(allf - Mod(sum + sf[u]))));
}
int main() {
  int u, v;
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (int)(n - 1); ++i) {
    scanf("%d%d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  if (m == 1) {
    printf("%lld\n", (1ll * n * (n - 1) / 2) % PP);
    return 0;
  }
  int t = max(n, m);
  fac[0] = rfac[0] = 1;
  for (int i = (1); i <= (int)(t); ++i) fac[i] = Mul(fac[i - 1], i);
  rfac[t] = Pow(fac[t], PP - 2);
  for (int i = (t - 1); i >= (int)(1); --i) rfac[i] = Mul(rfac[i + 1], i + 1);
  Dfs_init(1, 0);
  Dfs(1, 0, 0);
  for (int i = (1); i <= (int)(n); ++i) allf = Mod(allf + f[i]);
  Calc(1, 0, 0);
  printf("%d\n", Mod(Mul(ans1, Pow(2, PP - 2)) + ans2));
  return 0;
}