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;
mt19937 rnd(228);
const int M = 998244353;
const int P = 15311432;
const int B = (1 << 23);
const int N = 1e6 + 7;
const int K = 18;
int w[K][N];
int fact[N];
int rev_fact[N];
int sz[N];
int dp[N];
vector<int> g[N];
vector<int> ans[N];
vector<int> res[N];
inline int add(int a, int b) {
  return (a + b >= M ? a + b - M : a + b < 0 ? a + b + M : a + b);
}
inline int mul(int a, int b) { return (a * (long long)b) % M; }
inline int bin(int a, int n) {
  int res = 1;
  while (n) {
    if (n % 2 == 0) {
      a = mul(a, a);
      n /= 2;
    } else {
      res = mul(res, a);
      n--;
    }
  }
  return res;
}
int rev(int x, int bit) {
  int cur = 0;
  for (int i = 0; i < bit; i++) {
    if ((x >> i) & 1) {
      cur |= (1 << (bit - 1 - i));
    }
  }
  return cur;
}
vector<int> fft(const vector<int> &a, int bit) {
  int n = a.size();
  vector<int> f(n);
  for (int i = 0; i < n; i++) {
    f[rev(i, bit)] = a[i];
  }
  int bin = 0;
  for (int len = 1; len < n; len *= 2) {
    for (int st = 0; st < n; st += 2 * len) {
      for (int i = st; i < st + len; i++) {
        int t = f[i], b = mul(f[i + len], w[bin][i - st]);
        f[i] = add(t, b);
        f[i + len] = add(t, -b);
      }
    }
    bin++;
  }
  return f;
}
vector<int> mul(vector<int> a, vector<int> b) {
  int n = a.size(), m = b.size();
  int k = n + m;
  int len = 1;
  int cnt = 0;
  while (len < k) {
    len *= 2;
    cnt++;
  }
  k = len;
  while ((int)a.size() < k) {
    a.push_back(0);
  }
  while ((int)b.size() < k) {
    b.push_back(0);
  }
  a = fft(a, cnt);
  b = fft(b, cnt);
  for (int i = 0; i < k; i++) {
    a[i] = mul(a[i], b[i]);
  }
  a = fft(a, cnt);
  int rev = bin(k, M - 2);
  for (int i = 0; i < k; i++) {
    a[i] = mul(a[i], rev);
  }
  reverse(a.begin() + 1, a.end());
  while (!a.empty() && a.back() == 0) {
    a.pop_back();
  }
  return a;
}
vector<int> solve(int l, int r, const vector<int> &sz) {
  if (r - l == 1) {
    return {1, sz[l]};
  } else {
    int m = (l + r) / 2;
    return mul(solve(l, m, sz), solve(m, r, sz));
  }
}
int ret = 0;
int n, k;
void dfs(int v, int pr) {
  sz[v] = 1;
  vector<int> cur;
  for (int to : g[v]) {
    if (to != pr) {
      dfs(to, v);
      sz[v] += sz[to];
      cur.push_back(sz[to]);
    }
  }
  int have = (int)cur.size();
  if (!cur.empty()) {
    cur = solve(0, have, cur);
  } else {
    cur = {1};
  }
  ans[v] = cur;
  for (int i = 0; i < (int)cur.size() && i <= k; i++) {
    int vert = k - i;
    int ans = cur[i];
    int cnt = mul(fact[k], mul(ans, rev_fact[vert]));
    dp[v] = add(dp[v], cnt);
  }
}
void zhfs(int v, int pr, int have, int del_sum) {
  ret = add(ret, -mul(dp[v], del_sum));
  ret = add(ret, mul(dp[v], have));
  vector<int> new_cur = ans[v];
  new_cur.push_back(0);
  for (int i = (int)new_cur.size() - 2; i >= 0; i--) {
    new_cur[i + 1] = add(new_cur[i + 1], mul(new_cur[i], n - sz[v]));
  }
  map<int, int> press;
  for (int to : g[v]) {
    if (to != pr) {
      if (!press.count(sz[to])) {
        int calc_dp = 0;
        vector<int> me = new_cur;
        vector<int> cur = me;
        for (int i = 0; i < (int)cur.size(); i++) {
          if (i == 0) {
            cur[i] = me[i];
          } else {
            cur[i] = add(me[i], -mul(cur[i - 1], sz[to]));
          }
        }
        for (int i = 0; i < (int)cur.size() && i <= k; i++) {
          int vert = k - i;
          int ans = cur[i];
          int cnt = mul(fact[k], mul(ans, rev_fact[vert]));
          calc_dp = add(calc_dp, cnt);
        }
        press[sz[to]] = calc_dp;
      }
    }
  }
  for (int to : g[v]) {
    if (to != pr) {
      zhfs(to, v, add(have, press[sz[to]]), add(del_sum, dp[v]));
    }
  }
}
int main() {
  for (int j = 0; j < K; j++) {
    int cur = (1 << (j + 1));
    w[j][0] = 1;
    w[j][1] = P;
    for (int i = cur; i < B; i *= 2) {
      w[j][1] = mul(w[j][1], w[j][1]);
    }
    for (int i = 2; i < cur; i++) {
      w[j][i] = mul(w[j][i - 1], w[j][1]);
    }
  }
  fact[0] = 1;
  for (int i = 1; i < N; i++) {
    fact[i] = mul(fact[i - 1], i);
  }
  rev_fact[N - 1] = bin(fact[N - 1], M - 2);
  for (int i = N - 2; i >= 0; i--) {
    rev_fact[i] = mul(rev_fact[i + 1], i + 1);
  }
  cin >> n >> k;
  if (k == 1) {
    cout << n * (long long)(n - 1) / 2 % M << '\n';
    return 0;
  }
  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(0, -1);
  int me = 0;
  for (int i = 0; i < n; i++) {
    ret = add(ret, mul(me, dp[i]));
    me = add(me, dp[i]);
  }
  zhfs(0, -1, 0, 0);
  cout << ret << '\n';
}