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 = 100005;
const int mod = 998244353;
int n, kk, fac[N], inv[N];
vector<int> g[N];
void add(int& x, int y) { x = x + y < mod ? x + y : x + y - mod; }
int pw(int x, int y) {
  int t = 1;
  for (; y; y >>= 1) {
    if (y & 1) t = (long long)t * x % mod;
    x = (long long)x * x % mod;
  }
  return t;
}
void blmerge(vector<int>& a, vector<int>& b) {
  static int c[N * 2];
  for (int i = 0; i < ((int)((a).size())) + ((int)((b).size())); ++i) c[i] = 0;
  for (int i = 0; i < ((int)((a).size())); ++i) {
    for (int j = 0; j < ((int)((b).size())); ++j) {
      add(c[i + j], (long long)a[i] * b[j] % mod);
    }
  }
  a.resize(((int)((a).size())) + ((int)((b).size())) - 1);
  for (int i = 0; i < ((int)((a).size())); ++i) a[i] = c[i];
}
void fft(vector<int>& a, int n, int t) {
  static int pos[1 << 20];
  int i, j;
  j = __builtin_ctz(n) - 1;
  for (i = 0; i < n; ++i) {
    pos[i] = pos[i >> 1] >> 1 | ((i & 1) << j);
    if (pos[i] > i) swap(a[i], a[pos[i]]);
  }
  for (int d = 1; d < n; d *= 2) {
    int _w = pw(3, ((mod - 1) / d / 2));
    if (t == -1) _w = pw(_w, mod - 2);
    for (i = 0; i < n; i += d * 2) {
      int w = 1;
      for (j = 0; j < d; ++j) {
        int &A = a[i + j], &B = a[i + j + d], C = (long long)w * B % mod;
        B = A - C;
        if (B < 0) B += mod;
        A = A + C;
        if (A >= mod) A -= mod;
        w = (long long)w * _w % mod;
      }
    }
  }
  int nn = pw(n, mod - 2);
  if (t == -1)
    for (i = 0; i < n; ++i) a[i] = (long long)a[i] * nn % mod;
}
void fftmerge(vector<int>& a, vector<int>& b) {
  int d = ((int)((a).size())) + ((int)((b).size())) - 1, len = 1;
  for (; len <= max(((int)((a).size())), ((int)((b).size()))) * 2; len *= 2)
    ;
  a.resize(len, 0);
  b.resize(len, 0);
  fft(a, len, 1);
  fft(b, len, 1);
  for (int i = 0; i < len; ++i) a[i] = (long long)a[i] * b[i] % mod;
  fft(a, len, -1);
  a.resize(d);
}
void merge(vector<int>& a, vector<int>& b) {
  if (min(((int)((a).size())), ((int)((b).size()))) < 30)
    blmerge(a, b);
  else
    fftmerge(a, b);
}
void solve(vector<int> a[], int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  solve(a, l, mid);
  solve(a, mid + 1, r);
  merge(a[l], a[mid + 1]);
}
int f[N], sf[N], sz[N], ans[N];
bool cmpsz(int x, int y) { return sz[x] < sz[y]; }
int fa[N];
void dfs1(int x) {
  sz[x] = 1;
  int p = -1;
  for (int i = 0; i < ((int)((g[x]).size())); ++i) {
    if (g[x][i] == fa[x]) {
      p = i;
      continue;
    }
    fa[g[x][i]] = x;
    dfs1(g[x][i]);
    sz[x] += sz[g[x][i]];
  }
  if (~p) swap(g[x][p], g[x].back()), g[x].pop_back();
}
void dfs2(int x) {
  static vector<int> tmp[N];
  static vector<int> to, fap;
  int i, j;
  if (sz[x] == 1) {
    f[x] = sf[x] = 1;
    return;
  }
  sort(g[x].begin(), g[x].end(), cmpsz);
  for (i = 0; i < ((int)((g[x]).size())); ++i) {
    dfs2(g[x][i]);
    add(sf[x], sf[g[x][i]]);
  }
  for (i = 0; i < ((int)((g[x]).size())); ++i) {
    tmp[i].clear();
    tmp[i].push_back(1);
    tmp[i].push_back(sz[g[x][i]]);
  }
  solve(tmp, 0, ((int)((g[x]).size())) - 1);
  for (i = 0; i <= kk && i <= ((int)((g[x]).size())); ++i) {
    add(f[x], (long long)tmp[0][i] * fac[kk] % mod * inv[kk - i] % mod);
  }
  add(sf[x], f[x]);
  fap.clear();
  fap.push_back(1);
  fap.push_back(n - sz[x]);
  blmerge(tmp[0], fap);
  int pre = 0;
  for (i = 0; i < ((int)((g[x]).size())); ++i) {
    add(ans[x], (long long)pre * sf[g[x][i]] % mod);
    add(pre, sf[g[x][i]]);
  }
  int l, r;
  for (l = 0; l < ((int)((g[x]).size())); l = r) {
    int sub = 0;
    for (r = l; r < ((int)((g[x]).size())) && sz[g[x][r]] == sz[g[x][l]]; ++r) {
      add(sub, sf[g[x][r]]);
    }
    to.clear();
    to.resize(((int)((g[x]).size())) + 2, 0);
    int cut = pw(sz[g[x][l]], mod - 2);
    for (i = ((int)((g[x]).size())); i >= 0; --i) {
      to[i] = (long long)cut * (tmp[0][i + 1] - to[i + 1] + mod) % mod;
    }
    int out = 0;
    for (i = 0; i <= ((int)((g[x]).size())) && i <= kk; ++i) {
      add(out, (long long)to[i] * fac[kk] % mod * inv[kk - i] % mod);
    }
    add(ans[x], (long long)out * sub % mod);
  }
}
int main() {
  int i, j;
  scanf("%d%d", &n, &kk);
  for (fac[0] = i = 1; i < N; ++i) fac[i] = (long long)fac[i - 1] * i % mod;
  inv[N - 1] = pw(fac[N - 1], mod - 2);
  for (i = N - 1; i; --i) inv[i - 1] = (long long)inv[i] * i % mod;
  for (i = 2; i <= n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  if (kk == 1) return printf("%d\n", ((long long)n * (n - 1) / 2) % mod), 0;
  dfs1(1);
  dfs2(1);
  for (i = 1; i <= n; ++i) add(ans[0], ans[i]);
  printf("%d\n", ans[0]);
  return 0;
}