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;
int read() {
  char c = getchar();
  int d = 0, f = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; d = d * 10 + c - 48, c = getchar())
    ;
  return d * f;
}
const int mod = 998244353, G = 3;
const int N = 100001;
void inc(int& a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
void dec(int& a, int b) {
  a -= b;
  if (a < 0) a += mod;
}
int mul(int a, int b) { return (long long)a * b % mod; }
int mi(int a, int b) {
  int s = 1;
  for (; b; b >>= 1, a = (long long)a * a % mod)
    if (b & 1) s = (long long)s * a % mod;
  return s;
}
int n, m, sz[N], ft[N], ans;
vector<int> e[N];
void addedge(int x, int y) {
  e[x].push_back(y);
  e[y].push_back(x);
}
namespace fft {
vector<int> rev;
int _getup(int L) {
  int x = 1;
  while (x < L) x <<= 1;
  return x;
}
void _initrev(int L) {
  rev.resize(L);
  rev[0] = 0;
  for (int i = 1; i <= L - 1; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (L >> 1) : 0);
}
void _fft(vector<int>& a, int tp) {
  int L = ((int)a.size());
  for (int i = 1; i <= L - 1; ++i)
    if (rev[i] < i) swap(a[i], a[rev[i]]);
  for (int i = 2; i <= L; i <<= 1) {
    int I = i >> 1, w = mi(G, (mod - 1) / i);
    if (tp < 0) w = mi(w, mod - 2);
    for (int j = 0; j < L; j += i)
      for (int k = j, W = 1; k < j + I; ++k, W = mul(W, w)) {
        int A = a[k], B = mul(a[k + I], W);
        a[k] = a[k + I] = A;
        inc(a[k], B);
        dec(a[k + I], B);
      }
  }
  if (tp < 0) {
    int w = mi(L, mod - 2);
    for (int i = 0; i <= L - 1; ++i) a[i] = mul(a[i], w);
  }
}
vector<int> _mul(vector<int> a, vector<int> b, int eq = 0) {
  int L = ((int)a.size()) + ((int)b.size()) - 1;
  int Len = _getup(L);
  a.resize(Len);
  b.resize(Len);
  _initrev(Len);
  _fft(a, 1);
  if (eq)
    b = a;
  else
    _fft(b, 1);
  for (int i = 0; i <= Len - 1; ++i) a[i] = mul(a[i], b[i]);
  _fft(a, -1);
  a.resize(L);
  return a;
}
vector<int> _add(vector<int> a, vector<int> b) {
  if (((int)a.size()) < ((int)b.size())) a.resize(((int)b.size()));
  for (int i = 0; i <= ((int)b.size()) - 1; ++i) inc(a[i], b[i]);
  return a;
}
}  // namespace fft
using namespace fft;
pair<vector<int>, vector<int> > solve(vector<int> a, vector<int> b) {
  int Len = ((int)a.size()), m = Len / 2;
  vector<int> A, B;
  A.clear(), B.clear();
  if (Len == 1) {
    A.push_back(1);
    A.push_back(b[0]);
    B.push_back(a[0]);
    B.push_back(0);
    return make_pair(A, B);
  }
  pair<vector<int>, vector<int> > L, R;
  L.first.clear(), L.second.clear();
  R.first.clear(), R.second.clear();
  for (int i = 0; i <= m - 1; ++i) L.first.push_back(a[i]);
  for (int i = m; i <= Len - 1; ++i) R.first.push_back(a[i]);
  for (int i = 0; i <= m - 1; ++i) L.second.push_back(b[i]);
  for (int i = m; i <= Len - 1; ++i) R.second.push_back(b[i]);
  L = solve(L.first, L.second);
  R = solve(R.first, R.second);
  return make_pair(_mul(L.first, R.first),
                   _add(_mul(L.first, R.second), _mul(L.second, R.first)));
}
int dfs(int fa, int x) {
  sz[x] = 1;
  vector<int> v1, v2;
  v1.clear(), v2.clear();
  int sum = 0;
  for (int i = 0; i <= ((int)e[x].size()) - 1; ++i) {
    int y = e[x][i];
    if (y == fa) continue;
    int s = dfs(x, y);
    inc(ans, mul(sum, s));
    inc(sum, s);
    v1.push_back(s);
    v2.push_back(sz[y]);
    sz[x] += sz[y];
  }
  if (fa) v1.push_back(0), v2.push_back(n - sz[x]);
  pair<vector<int>, vector<int> > S = solve(v1, v2);
  vector<int>&A = S.first, &B = S.second;
  for (int i = 0; i <= m; ++i) {
    if (i >= ((int)B.size()) && i >= ((int)A.size())) break;
    if (i < ((int)B.size())) inc(ans, mul(B[i], ft[i]));
    if (i + 1 < ((int)A.size())) dec(A[i + 1], mul(A[i], n - sz[x]));
    if (i < ((int)A.size())) inc(sum, mul(A[i], ft[i]));
  }
  return sum;
}
int main() {
  n = read(), m = read();
  if (n == 1) {
    printf("0\n");
    return 0;
  }
  for (int i = 2; i <= n; ++i) addedge(read(), read());
  if (m == 1) {
    printf("%d\n", (long long)n * (n - 1) / 2 % mod);
    return 0;
  }
  ft[0] = 1;
  for (int i = 1; i <= m; ++i) ft[i] = mul(ft[i - 1], m - i + 1);
  dfs(0, 1);
  printf("%d\n", ans);
}