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 char getch() {
  static char buf[10000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long read() {
  long long s = 0, f = 1;
  char ch = getch();
  while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getch();
  while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getch();
  return s * f;
}
void File() {
  freopen(
      "filename"
      ".in",
      "r", stdin);
  freopen(
      "filename"
      ".out",
      "w", stdout);
}
namespace Solver {
const int MaxN = 2e5 + 5;
const int Mod = 998244353;
int rev[MaxN], W0[MaxN], iW0[MaxN], W[MaxN];
long long ksm(long long x, long long y, long long p) {
  long long res = 1;
  for (; y; y >>= 1, x = x * x % p)
    if (y & 1) res = res * x % p;
  return res;
}
void Makerv(int N, int Len) {
  for (int i = 1; i < N; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (Len - 1));
}
void NTT(vector<long long> &A, int N, int f) {
  for (int i = 0; i < N; i++)
    if (rev[i] > i) swap(A[i], A[rev[i]]);
  for (int i = 1; i < N; i <<= 1) {
    long long wn = (f == 1) ? W0[i] : iW0[i];
    W[0] = 1;
    for (int j = 1; j < i; j++) W[j] = 1ll * W[j - 1] * wn % Mod;
    for (int j = 0; j < N; j += (i << 1)) {
      for (int k = 0; k < i; k++) {
        long long x = A[j + k], y = W[k] * A[j + i + k] % Mod;
        A[j + k] = (x + y) % Mod;
        A[j + i + k] = (x - y + Mod) % Mod;
      }
    }
  }
  if (f == 1) return;
  long long Inv = ksm(N, Mod - 2, Mod);
  for (int i = 0; i < N; i++) A[i] = A[i] * Inv % Mod;
}
long long fac[MaxN], inv[MaxN], ifac[MaxN];
void Init(int N = 2e5) {
  fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
  for (int i = 2; i <= N; i++) {
    fac[i] = fac[i - 1] * i % Mod;
    inv[i] = Mod - Mod / i * inv[Mod % i] % Mod;
    ifac[i] = ifac[i - 1] * inv[i] % Mod;
  }
  for (int i = 1; i <= N; i <<= 1) {
    W0[i] = ksm(3, (Mod - 1) / (i << 1), Mod);
    iW0[i] = ksm(W0[i], Mod - 2, Mod);
  }
}
int n, k;
struct Edge {
  int to, nxt;
};
Edge e[MaxN << 1];
int h[MaxN], cnt;
void Add_Edge(int x, int y) {
  e[++cnt] = (Edge){y, h[x]};
  h[x] = cnt;
}
long long sum[MaxN], Ans;
long long A[MaxN], B[MaxN];
int siz[MaxN];
vector<long long> F, G;
void Divide(int l, int r, vector<long long> &F, vector<long long> &G) {
  if (l == r) {
    F.resize(2);
    G.resize(1);
    F[0] = 1;
    F[1] = B[l];
    G[0] = A[l];
    return;
  }
  int mid = (l + r) >> 1;
  vector<long long> Fl, Fr, Gl, Gr;
  Divide(l, mid, Fl, Gl);
  Divide(mid + 1, r, Fr, Gr);
  int N, Len, l1, l2;
  l1 = mid - l + 1, l2 = r - mid;
  Len = ceil(log2(l1 + l2 + 1));
  N = 1 << Len;
  Makerv(N, Len);
  F.resize(N), G.resize(N);
  Fl.resize(N), Fr.resize(N);
  Gl.resize(N), Gr.resize(N);
  Gl[l1] = Gr[l2] = 0;
  for (int i = l1 + 1; i < N; i++) Fl[i] = Gl[i] = 0;
  for (int i = l2 + 1; i < N; i++) Fr[i] = Gr[i] = 0;
  NTT(Fl, N, 1);
  NTT(Fr, N, 1);
  NTT(Gl, N, 1);
  NTT(Gr, N, 1);
  for (int i = 0; i < N; i++) {
    F[i] = Fl[i] * Fr[i] % Mod;
    G[i] = (Fl[i] * Gr[i] % Mod + Gl[i] * Fr[i] % Mod) % Mod;
  }
  NTT(F, N, -1);
  NTT(G, N, -1);
  G[r - l + 1] = 0;
  for (int i = r - l + 2; i < N; i++) F[i] = G[i] = 0;
}
void dfs(int x, int fa) {
  sum[x] = 0;
  siz[x] = 1;
  for (int i = h[x]; i; i = e[i].nxt) {
    int y = e[i].to;
    if (y == fa) continue;
    dfs(y, x);
    siz[x] += siz[y];
    Ans = (Ans + sum[x] * sum[y] % Mod) % Mod;
    sum[x] = (sum[x] + sum[y]) % Mod;
  }
  int tot = 0;
  for (int i = h[x]; i; i = e[i].nxt) {
    int y = e[i].to;
    if (y == fa) continue;
    ++tot;
    A[tot] = sum[y];
    B[tot] = siz[y];
  }
  if (!tot) return sum[x] = 1, void();
  Divide(1, tot, F, G);
  G.resize(tot + 1);
  G[tot] = 0;
  for (int i = tot - 1; i >= 0; i--)
    G[i + 1] = (G[i + 1] + (n - siz[x]) * G[i] % Mod) % Mod;
  for (int i = 0; i <= min(k, tot); i++) {
    Ans = (Ans + G[i] * fac[k] % Mod * ifac[k - i] % Mod) % Mod;
    sum[x] = (sum[x] + F[i] * fac[k] % Mod * ifac[k - i] % Mod) % Mod;
  }
}
void Main() {
  Init();
  n = read(), k = read();
  if (k == 1) return cout << 1ll * n * (n - 1) / 2 % Mod << "\n", void();
  for (int i = 1; i < n; i++) {
    int x = read(), y = read();
    Add_Edge(x, y);
    Add_Edge(y, x);
  }
  dfs(1, 0);
  cout << Ans << "\n";
}
}  // namespace Solver
int main() {
  Solver::Main();
  return 0;
}