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;
void file_put() {
  freopen("filename.in", "r", stdin);
  freopen("filename.out", "w", stdout);
}
long long Pow(long long x, long long k, long long _p) {
  long long ans = 1;
  for (; k; k >>= 1, x = x * x % _p)
    if (k & 1) (ans *= x) %= _p;
  return ans;
}
const int N = 100005, _p = 998244353;
const int _M = N, _N = N;
template <class V>
struct FT {
  vector<V> aa, bb;
  V w[2][_M * 2 + 5], rev[_M * 2 + 5], tmp;
  void FFT(vector<V> &A, int m, int op) {
    int N = 1 << m;
    V w0 = Pow(3, (_p - 1) / N, _p);
    w[0][0] = w[1][0] = 1;
    for (int i = (1); i < (N); i++)
      w[0][i] = w[1][N - i] = (long long)w[0][i - 1] * w0 % _p;
    for (int i = (1); i < (N); i++)
      rev[i] = (rev[i >> 1] >> 1) | (i & 1) << m - 1;
    for (int i = (0); i < (N); i++)
      if (i < rev[i]) swap(A[i], A[rev[i]]);
    for (int i = 1; i < N; i <<= 1)
      for (int j = 0, t = N / (i << 1); j < N; j += i << 1)
        for (int k = j, l = 0; k < j + i; k++, l += t) {
          V x = A[k], y = (long long)w[op][l] * A[k + i] % _p;
          A[k] = (x + y) % _p, A[k + i] = (x - y + _p) % _p;
        }
    if (op) {
      tmp = Pow(N, _p - 2, _p);
      for (int i = (0); i < (N); i++) A[i] = 1ll * A[i] * tmp % _p;
    }
  }
  vector<V> multiply(vector<V> A, vector<V> B, vector<V> *C = NULL,
                     int op = 0) {
    int lena = A.size(), lenb = B.size(), len = 1, L = 0;
    aa = A, bb = B;
    while (len < lena + lenb - 1) len <<= 1, ++L;
    aa.resize(len), bb.resize(len);
    if (op) reverse((bb).begin(), (bb).end());
    FFT(aa, L, 0), FFT(bb, L, 0);
    if (!C) C = &A;
    (*C).resize(len);
    for (int i = (0); i < (len); i++) (*C)[i] = (long long)aa[i] * bb[i] % _p;
    FFT(*C, L, 1);
    if (op) reverse((*C).begin(), (*C).end());
    (*C).resize(lena + lenb - 1);
    return *C;
  }
};
int n, k, x, y, siz[N];
vector<int> V[N], P[N];
long long ans = 0, s = 0, fac[N], inv[N], dp[N];
FT<int> T;
vector<int> solve(int l, int r, const vector<int> &a) {
  if (l == r) return vector<int>{1, a[l]};
  int mid = l + r >> 1;
  return T.multiply(solve(l, mid, a), solve(mid + 1, r, a));
}
void dfs(int x, int p) {
  siz[x] = 1;
  for (auto y : V[x]) {
    if (y == p) continue;
    dfs(y, x), siz[x] += siz[y], P[x].push_back(siz[y]);
  }
  if (P[x].empty())
    P[x].push_back(1);
  else
    P[x] = solve(0, (int)P[x].size() - 1, P[x]);
  for (int i = (0); i < (min(k, (int)P[x].size() - 1) + 1); i++)
    dp[x] += inv[k - i] % _p * P[x][i] % _p;
  dp[x] %= _p, (dp[x] *= fac[k]) %= _p;
}
void dfs(int x, int p, long long s1, long long s2) {
  ans += dp[x] * (s1 - s2) % _p, ans %= _p;
  P[x].push_back(0);
  map<int, int> M;
  for (int i = ((int)P[x].size()) - 1; i >= (1); i--)
    P[x][i] += (long long)P[x][i - 1] * (n - siz[x]) % _p, P[x][i] %= _p;
  for (auto y : V[x]) {
    if (y == p || M.find(siz[y]) != M.end()) continue;
    long long ret = 0;
    vector<int> tmp = P[x];
    for (int i = (0); i < ((int)tmp.size() - 1); i++)
      tmp[i + 1] -= (long long)tmp[i] * siz[y] % _p, tmp[i + 1] %= _p;
    for (int i = (0); i < (min(k, (int)tmp.size() - 1) + 1); i++)
      ret += tmp[i] * fac[k] % _p * inv[k - i] % _p, ret %= _p;
    M[siz[y]] = ret;
  }
  for (auto y : V[x]) {
    if (y == p) continue;
    dfs(y, x, (s1 + M[siz[y]]) % _p, (s2 + dp[x]) % _p);
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  scanf("%d%d", &n, &k);
  for (int i = (1); i < (n); i++)
    scanf("%d%d", &x, &y), V[x].push_back(y), V[y].push_back(x);
  fac[0] = inv[0] = inv[1] = 1;
  for (int i = (2); i < (N); i++) inv[i] = (_p - _p / i) * inv[_p % i] % _p;
  for (int i = (1); i < (N); i++)
    inv[i] = inv[i - 1] * inv[i] % _p, fac[i] = fac[i - 1] * i % _p;
  if (k == 1) {
    cout << (long long)n * (n - 1) / 2 % _p << "\n";
    return 0;
  }
  dfs(1, 0), dfs(1, 0, 0, 0);
  for (int i = (1); i < (n + 1); i++)
    ans += dp[i] * s % _p, s += dp[i], ans %= _p, s %= _p;
  cout << (ans + _p) % _p << "\n";
  return 0;
}