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 long long Getint() {
  char ch = getchar();
  long long x = 0, fh = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') fh = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    (x *= 10) += ch ^ 48;
    ch = getchar();
  }
  return x * fh;
}
const long long mod = 998244353;
const int N = 400005;
inline long long Inc(long long x, long long y) {
  return (x += y) >= mod ? x - mod : x;
}
inline long long Dec(long long x, long long y) {
  return (x -= y) < 0 ? x + mod : x;
}
inline long long Ksm(long long x, long long y) {
  long long tmp = 1;
  while (y) {
    if (y & 1) tmp = tmp * x % mod;
    y >>= 1;
    if (y) x = x * x % mod;
  }
  return tmp;
}
long long K, n, fc[N], fiv[N], inv[N];
vector<int> G[N];
int lst, rev[N];
long long pwi[2][25], wn[N];
inline void initpw() {
  for (int i = 1, k = 0; i < N; i <<= 1, k++) {
    pwi[0][k] = Ksm(3, (mod - 1) / (i << 1));
    pwi[1][k] = Ksm(3, -(mod - 1) / (i << 1) + mod - 1);
  }
}
inline int Make(int len) { return 1 << int(ceil(log2(len))); }
inline int Trans(int len) {
  int l = ceil(log2(len));
  len = 1 << l;
  for (int i = 0; i <= len - 1; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << l - 1);
  return lst = len;
}
inline void NTT(vector<long long> &F, int fir, int len, int f) {
  if (lst != len) Trans(len);
  if (f == 1) F.resize(len);
  for (int i = 0; i <= len - 1; i++)
    if (rev[i] < i) swap(F[rev[i]], F[i]);
  for (int i = 1, k = 0; i < len; i <<= 1, k++) {
    long long wi = f == 1 ? pwi[0][k] : pwi[1][k];
    wn[0] = 1;
    for (int j = 1; j <= i - 1; j++) wn[j] = wn[j - 1] * wi % mod;
    for (int j = 0; j < len; j += i << 1) {
      for (int k = 0; k < i; k++) {
        long long x = F[j + k], y = F[i + j + k] * wn[k] % mod;
        F[j + k] = Inc(x, y);
        F[i + j + k] = Dec(x, y);
      }
    }
  }
  if (f == 1) return;
  long long iv = inv[len];
  for (int i = 0; i <= fir - 1; i++) F[i] = F[i] * iv % mod;
  F.resize(fir);
}
inline vector<long long> operator*(vector<long long> A, vector<long long> B) {
  if (A.size() == 0) return A;
  if (B.size() == 0) return B;
  int len = A.size() + B.size() - 1, l = Make(len);
  NTT(A, A.size(), l, 1);
  NTT(B, B.size(), l, 1);
  for (int i = 0; i <= l - 1; i++) A[i] = A[i] * B[i] % mod;
  NTT(A, len, l, -1);
  return A;
}
vector<long long> F[N], Lt;
map<int, long long> mp[N];
inline long long Div(int u, int sz) {
  if (mp[u].count(sz)) return mp[u][sz];
  vector<long long> A = F[u];
  vector<long long> C(A.size() - 1);
  long long iv = inv[sz];
  for (int i = int(A.size()) - 1; i >= 1; i--) {
    C[i - 1] = A[i] * iv % mod;
    A[i - 1] = Dec(A[i - 1], C[i - 1]);
  }
  long long tmp = 0;
  for (int i = 0; i <= int(C.size()) - 1; i++) {
    if (i > K) break;
    (tmp += C[i] * fiv[K - i]) %= mod;
  }
  return mp[u][sz] = tmp;
}
inline vector<long long> CDQ1(int l = 0, int r = int(Lt.size()) - 1) {
  if (r < l) {
    vector<long long> t(1);
    t[0] = 1;
    return t;
  } else if (l == r) {
    vector<long long> t(2);
    t[1] = Lt[l];
    t[0] = 1;
    return t;
  }
  int mid = l + r >> 1;
  return CDQ1(l, mid) * CDQ1(mid + 1, r);
}
int sz[N];
long long dp[N];
void Dfs1(int u, int fa) {
  sz[u] = 1;
  dp[u] = 0;
  for (int v : G[u]) {
    if (v == fa) continue;
    Dfs1(v, u);
    sz[u] += sz[v];
    dp[u] = Inc(dp[u], dp[v]);
  }
  Lt.clear();
  for (int v : G[u]) {
    if (v == fa) continue;
    Lt.push_back(sz[v]);
  }
  if (fa) Lt.push_back(n - sz[u]);
  F[u] = CDQ1();
  if (fa) {
    dp[u] = Inc(dp[u], Div(u, n - sz[u]));
  } else {
    for (int i = 0; i <= int(F[u].size()) - 1; i++) {
      if (i > K) break;
      (dp[u] += F[u][i] * fiv[K - i]) %= mod;
    }
  }
}
long long Ans = 0;
void Dfs2(int u, int fa) {
  long long su = 0;
  for (int v : G[u]) {
    if (v == fa) continue;
    Dfs2(v, u);
    (Ans += su * dp[v]) %= mod;
    su = Inc(su, dp[v]);
  }
  for (int v : G[u]) {
    if (v == fa) continue;
    long long val = Div(u, sz[v]);
    (Ans += val * dp[v]) %= mod;
  }
}
int main() {
  int x, y, z;
  fc[0] = fc[1] = inv[0] = inv[1] = fiv[0] = fiv[1] = 1;
  for (int i = 2; i <= N - 1; i++) {
    fc[i] = fc[i - 1] * i % mod;
    inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    fiv[i] = fiv[i - 1] * inv[i] % mod;
  }
  initpw();
  n = Getint();
  K = Getint();
  for (int i = 2; i <= n; i++) {
    x = Getint();
    y = Getint();
    G[x].push_back(y);
    G[y].push_back(x);
  }
  if (K == 1) {
    cout << n * (n - 1) / 2 % mod << '\n';
    return 0;
  }
  Dfs1(1, 0);
  Dfs2(1, 0);
  Ans = Ans % mod * Ksm(fc[K], 2) % mod;
  cout << (Ans % mod + mod) % mod << '\n';
  return 0;
}