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 = 3e5 + 5;
const int mod = 998244353;
const int g = 3;
int Pow(long long a, int x, const int &mod) {
  long long res = 1;
  while (x) {
    if (x & 1) (res *= a) %= mod;
    (a *= a) %= mod;
    x >>= 1;
  }
  return res;
}
void NTT(int *a, int n, int rev) {
  for (int i = 0, j = 0; i < n; ++i) {
    if (i > j) swap(a[i], a[j]);
    for (int k = n >> 1; (j ^= k) < k; k >>= 1)
      ;
  }
  for (int i = 2; i <= n; i <<= 1) {
    int m = i >> 1;
    int w = Pow(g, (mod - 1) / i, mod);
    if (rev == -1) w = Pow(w, mod - 2, mod);
    for (int j = 0; j < n; j += i) {
      long long Wx = 1;
      for (int k = 0; k != m; k++) {
        long long z = a[j + m + k] * Wx % mod;
        a[j + m + k] = a[j + k] - z + mod;
        if (a[j + m + k] >= mod) a[j + m + k] -= mod;
        a[j + k] = a[j + k] + z;
        if (a[j + k] >= mod) a[j + k] -= mod;
        Wx = Wx * w % mod;
      }
    }
  }
  if (rev == -1) {
    long long inv = Pow(n, mod - 2, mod);
    for (int i = 0; i < n; i++) a[i] = a[i] * inv % mod;
  }
}
int len, A[N], B[N];
int n, k, size[N];
vector<int> G[N];
vector<int> poly[N];
long long ans, sum, F[N], sumF[N];
long long fac[N], inv[N];
vector<int> calc(vector<int> &sz) {
  vector<int> res;
  res.resize(sz.size() + 1);
  if (sz.size() == 0) {
    res[0] = 1;
    return res;
  }
  if (sz.size() == 1) {
    res[0] = 1;
    res[1] = sz[0];
    return res;
  }
  int mid = sz.size() >> 1;
  vector<int> l, r;
  for (int i = 0; i < mid; ++i) l.push_back(sz[i]);
  for (int i = mid; i < sz.size(); ++i) r.push_back(sz[i]);
  l = calc(l);
  r = calc(r);
  len = 1;
  while (len <= l.size() + r.size() - 2) len <<= 1;
  for (int i = 0; i < len; ++i) A[i] = B[i] = 0;
  for (int i = 0; i < l.size(); ++i) A[i] = l[i];
  for (int i = 0; i < r.size(); ++i) B[i] = r[i];
  NTT(A, len, 1);
  NTT(B, len, 1);
  for (int i = 0; i < len; ++i) A[i] = (long long)A[i] * B[i] % mod;
  NTT(A, len, -1);
  for (int i = 0; i <= sz.size(); ++i) res[i] = A[i];
  return res;
}
void dfs(int x, int f) {
  size[x] = 1;
  vector<int> V;
  for (int u : G[x]) {
    if (u == f) continue;
    dfs(u, x);
    size[x] += size[u];
    V.push_back(size[u]);
    sumF[x] += sumF[u];
    if (sumF[x] >= mod) sumF[x] -= mod;
  }
  poly[x] = calc(V);
  for (int i = 0; i < poly[x].size(); ++i) {
    if (i > k) break;
    F[x] += poly[x][i] * fac[k] % mod * inv[k - i];
    F[x] %= mod;
  }
  sum += F[x];
  if (sum >= mod) sum -= mod;
  sumF[x] += F[x];
  if (sumF[x] >= mod) sumF[x] -= mod;
}
void div(vector<int> &p, int s) {
  vector<int> q;
  q.resize(p.size() - 1);
  s = fac[s - 1] * inv[s] % mod;
  for (int i = q.size() - 1; i >= 0; --i) {
    q[i] = (long long)p[i + 1] * s % mod;
    p[i] += mod - q[i];
    if (p[i] >= mod) p[i] -= mod;
  }
  p = q;
}
void mul(vector<int> &p, int s) {
  p.push_back(0);
  for (int i = p.size() - 2; i >= 0; --i) {
    p[i + 1] += (long long)p[i] * s % mod;
    if (p[i + 1] >= mod) p[i + 1] -= mod;
  }
}
long long value(vector<int> &poly) {
  long long res = 0;
  for (int i = 0; i < poly.size(); ++i) {
    if (i > k) break;
    res += poly[i] * fac[k] % mod * inv[k - i];
    res %= mod;
  }
  return res;
}
void add(vector<int> &poly) {
  for (int i = 0; i < poly.size(); ++i) {
    if (i > k) break;
    sum += poly[i] * fac[k] % mod * inv[k - i];
    sum %= mod;
  }
}
void sub(vector<int> &poly) {
  for (int i = 0; i < poly.size(); ++i) {
    if (i > k) break;
    sum += (long long)mod * mod - poly[i] * fac[k] % mod * inv[k - i];
    sum %= mod;
  }
}
void dfs2(int x, int f) {
  sort(G[x].begin(), G[x].end(),
       [](int i, int j) { return size[i] < size[j]; });
  if (f) G[x].erase(find(G[x].begin(), G[x].end(), f));
  int presize = -1;
  for (int i = 0; i < G[x].size(); ++i) {
    int uu, u = G[x][i];
    long long presum = sum;
    sub(poly[x]);
    div(poly[x], size[u]);
    if (x != 1) mul(poly[x], n - size[x]);
    add(poly[x]);
    ans += F[u] * (sum - sumF[u] + mod);
    ans %= mod;
    long long tmp = value(poly[x]);
    ans += tmp * sumF[u];
    ans %= mod;
    dfs2(u, x);
    while (i + 1 < G[x].size() && size[uu = G[x][i + 1]] == size[u]) {
      ans += F[uu] * (sum - sumF[uu] + mod);
      ans %= mod;
      ans += tmp * sumF[uu];
      ans %= mod;
      dfs2(uu, x);
      ++i;
    }
    mul(poly[x], size[u]);
    if (x != 1) div(poly[x], n - size[x]);
    sum = presum;
  }
}
int main() {
  cin >> n >> k;
  for (int i = 1; i < n; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    G[x].push_back(y);
    G[y].push_back(x);
  }
  if (k == 1) {
    cout << (long long)n * (n - 1) / 2 % mod << endl;
    return 0;
  }
  fac[0] = 1;
  for (int i = 1; i < N; ++i) fac[i] = fac[i - 1] * i % mod;
  inv[N - 1] = Pow(fac[N - 1], mod - 2, mod);
  for (int i = N - 2; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
  dfs(1, 0);
  dfs2(1, 0);
  cout << ans * Pow(2, mod - 2, mod) % mod;
}