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 = 500010, P = 998244353;
int n, k, cnt, G[N], f[N], g[N], fac[N], inv[N];
struct edge {
  int t, nx;
} E[N << 1];
inline void addedge(int x, int y) {
  E[++cnt].t = y;
  E[cnt].nx = G[x];
  G[x] = cnt;
  E[++cnt].t = x;
  E[cnt].nx = G[y];
  G[y] = cnt;
}
int num, w[2][N], rev[N], size[N];
inline int Pow(int x, int y) {
  int ret = 1;
  for (; y; y >>= 1, x = 1LL * x * x % P)
    if (y & 1) ret = 1LL * ret * x % P;
  return ret;
}
inline void Pre(const int &n) {
  int g = Pow(3, (P - 1) / (num = n));
  w[1][0] = w[0][0] = 1;
  for (int i = 1; i < num; i++) w[1][i] = 1LL * w[1][i - 1] * g % P;
  for (int i = 1; i < num; i++) w[0][i] = w[1][num - i];
  fac[0] = 1;
  for (int i = 1; i <= num; i++) fac[i] = 1LL * fac[i - 1] * i % P;
  inv[1] = 1;
  for (int i = 2; i <= num; i++) inv[i] = 1LL * (P - P / i) * inv[P % i] % P;
  inv[0] = 1;
  for (int i = 1; i <= num; i++) inv[i] = 1LL * inv[i] * inv[i - 1] % P;
}
inline void NTT(int *a, int n, int r) {
  for (int i = 1; i < n; i++)
    if (rev[i] > i) swap(a[i], a[rev[i]]);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += (i << 1))
      for (int k = 0; k < i; k++) {
        int x = a[j + k], y = 1LL * a[j + k + i] * w[r][num / (i << 1) * k] % P;
        a[j + k] = (x + y) % P;
        a[j + k + i] = (x + P - y) % P;
      }
  if (!r)
    for (int i = 0, iv = Pow(n, P - 2); i < n; i++) a[i] = 1LL * a[i] * iv % P;
}
vector<int> operator*(vector<int> a, vector<int> b) {
  vector<int> ret;
  ret.resize(a.size() + b.size() - 1);
  if (1LL * a.size() * b.size() <= 10000) {
    for (int i = 0; i < a.size(); i++)
      for (int j = 0; j < b.size(); j++)
        ret[i + j] = (ret[i + j] + 1LL * a[i] * b[j]) % P;
    return ret;
  }
  int m, L = 0;
  for (m = 1; m <= ret.size(); m <<= 1, L++)
    ;
  m <<= 1;
  for (int i = 1; i < m; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L);
  static int A[N], B[N];
  for (int i = 0; i < a.size(); i++) A[i] = a[i];
  for (int i = 0; i < b.size(); i++) B[i] = b[i];
  NTT(A, m, 1);
  NTT(B, m, 1);
  for (int i = 0; i < m; i++) A[i] = 1LL * A[i] * B[i] % P;
  NTT(A, m, 0);
  for (int i = 0; i < ret.size(); i++) ret[i] = A[i];
  for (int i = 0; i < m; i++) A[i] = B[i] = 0;
  return ret;
}
vector<int> solve(vector<vector<int> > &a, int l, int r) {
  if (l == r) return a[l];
  int mid = l + r >> 1;
  return solve(a, l, mid) * solve(a, mid + 1, r);
}
int ans = 0, vis[N];
void dfs(int x, int fa) {
  size[x] = 1;
  vector<vector<int> > c;
  for (int i = G[x]; i; i = E[i].nx)
    if (E[i].t != fa) {
      dfs(E[i].t, x);
      size[x] += size[E[i].t];
      ans = (ans + 1LL * g[x] * g[E[i].t]) % P;
      g[x] = (g[x] + g[E[i].t]) % P;
    }
  for (int i = G[x]; i; i = E[i].nx)
    if (E[i].t != fa) {
      c.push_back(vector<int>{1, size[E[i].t]});
    }
  vector<int> cur;
  if (c.empty())
    cur = vector<int>{1};
  else
    cur = solve(c, 0, c.size() - 1);
  for (int i = 0; i < cur.size() && (i < k || (i == k && k > 1)); i++)
    f[x] = (f[x] + 1LL * cur[i] * fac[k] % P * inv[k - i]) % P;
  g[x] = (g[x] + f[x]) % P;
  vector<int> tmp = cur;
  tmp.push_back(0);
  for (int i = tmp.size() - 1; i; i--)
    tmp[i] = (tmp[i] + 1LL * tmp[i - 1] * (n - size[x])) % P;
  for (int i = G[x]; i; i = E[i].nx)
    if (E[i].t != fa) vis[size[E[i].t]] = 0;
  for (int i = G[x]; i; i = E[i].nx)
    if (E[i].t != fa) {
      if (!vis[size[E[i].t]]) {
        vector<int> c = tmp;
        for (int j = 1; j < c.size(); j++)
          c[j] = (c[j] - 1LL * c[j - 1] * size[E[i].t]) % P;
        c.resize(c.size() - 1);
        int val = 0;
        for (int j = 0; j < c.size() && (j < k || (j == k && k > 1)); j++)
          val = (val + 1LL * c[j] * fac[k] % P * inv[k - j]) % P;
        vis[size[E[i].t]] = val;
      }
      int val = vis[size[E[i].t]];
      ans = (ans + 1LL * g[E[i].t] * val) % P;
    }
}
int main() {
  scanf("%d%d", &n, &k);
  int m;
  for (m = 1; m <= n; m <<= 1)
    ;
  Pre(m << 1);
  for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), addedge(x, y);
  dfs(1, 0);
  printf("%d\n", (ans + P) % P);
  return 0;
}