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 MAXN = 1e5 + 5;
const int md = 998244353;
inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}
inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}
inline int mul(int a, int b) { return (int)((long long)a * b % md); }
inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}
inline int inv(int a) {
  a %= md;
  if (a < 0) a += md;
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += md;
  return u;
}
namespace ntt {
int base = 1;
vector<int> roots = {0, 1};
vector<int> rev = {0, 1};
int max_base = -1;
int root = -1;
void init() {
  int tmp = md - 1;
  max_base = 0;
  while (tmp % 2 == 0) {
    tmp /= 2;
    max_base++;
  }
  root = 2;
  while (true) {
    if (power(root, 1 << max_base) == 1) {
      if (power(root, 1 << (max_base - 1)) != 1) {
        break;
      }
    }
    root++;
  }
}
void ensure_base(int nbase) {
  if (max_base == -1) {
    init();
  }
  if (nbase <= base) {
    return;
  }
  assert(nbase <= max_base);
  rev.resize(1 << nbase);
  for (int i = 0; i < (1 << nbase); i++) {
    rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
  }
  roots.resize(1 << nbase);
  while (base < nbase) {
    int z = power(root, 1 << (max_base - 1 - base));
    for (int i = 1 << (base - 1); i < (1 << base); i++) {
      roots[i << 1] = roots[i];
      roots[(i << 1) + 1] = mul(roots[i], z);
    }
    base++;
  }
}
void fft(vector<int> &a) {
  int n = a.size();
  assert((n & (n - 1)) == 0);
  int zeros = __builtin_ctz(n);
  ensure_base(zeros);
  int shift = base - zeros;
  for (int i = 0; i < n; i++) {
    if (i < (rev[i] >> shift)) {
      swap(a[i], a[rev[i] >> shift]);
    }
  }
  for (int k = 1; k < n; k <<= 1) {
    for (int i = 0; i < n; i += 2 * k) {
      for (int j = 0; j < k; j++) {
        int x = a[i + j];
        int y = mul(a[i + j + k], roots[j + k]);
        a[i + j] = x + y - md;
        if (a[i + j] < 0) a[i + j] += md;
        a[i + j + k] = x - y + md;
        if (a[i + j + k] >= md) a[i + j + k] -= md;
      }
    }
  }
}
vector<int> multiply(vector<int> a, vector<int> b, int eq = 0) {
  int need = a.size() + b.size() - 1;
  int nbase = 0;
  while ((1 << nbase) < need) nbase++;
  ensure_base(nbase);
  int sz = 1 << nbase;
  a.resize(sz);
  b.resize(sz);
  fft(a);
  if (eq)
    b = a;
  else
    fft(b);
  int inv_sz = inv(sz);
  for (int i = 0; i < sz; i++) {
    a[i] = mul(mul(a[i], b[i]), inv_sz);
  }
  reverse(a.begin() + 1, a.end());
  fft(a);
  a.resize(need);
  return a;
}
vector<int> square(vector<int> a) { return multiply(a, a, 1); }
};  // namespace ntt
int N, K;
vector<int> E[MAXN];
int subtree[MAXN];
int down[MAXN];
vector<int> glob;
int choose[MAXN];
int ans;
void load() {
  scanf("%d%d", &N, &K);
  for (int i = 1; i < N; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    E[x].push_back(y);
    E[y].push_back(x);
  }
}
int calc(int x, int p) {
  subtree[x] = 1;
  for (auto it : E[x])
    if (it != p) subtree[x] += calc(it, x);
  return subtree[x];
}
vector<int> dac(int lo, int hi) {
  if (lo >= hi) return {1};
  if (hi - lo == 1) return {glob[lo], 1};
  int mid = (lo + hi) / 2;
  return ntt::multiply(dac(lo, mid), dac(mid, hi));
}
void horner(vector<int> &P, int zero) {
  int sz = P.size();
  vector<int> Q = P;
  P[sz - 1] = 0;
  for (int i = sz - 2; i >= 0; i--) {
    P[i] = Q[i + 1];
    sub(P[i], mul(zero, P[i + 1]));
  }
  P.pop_back();
}
int get(vector<int> P) {
  reverse(P.begin(), P.end());
  int res = 0;
  for (int i = 0; i < min((int)P.size(), K + 1); i++)
    add(res, mul(choose[i], P[i]));
  return res;
}
int dfs(int x, int p) {
  unordered_map<int, int> tot;
  vector<int> curr;
  for (auto it : E[x])
    if (it != p) {
      add(tot[subtree[it]], dfs(it, x));
      curr.push_back(subtree[it]);
    }
  if (x > 1) curr.push_back(N - subtree[x]);
  glob = curr;
  vector<int> poly = dac(0, (int)glob.size());
  vector<int> d = poly;
  if (x > 1) horner(d, N - subtree[x]);
  down[x] = get(d);
  int sum = 0;
  for (auto it : tot) {
    vector<int> tmp = poly;
    horner(tmp, it.first);
    add(ans, mul(get(tmp), it.second));
    add(sum, it.second);
  }
  sub(ans, mul(down[x], sum));
  add(sum, down[x]);
  return sum;
}
int solve() {
  if (K == 1) return (long long)N * (N - 1) / 2 % md;
  calc(1, 0);
  choose[0] = 1;
  for (int i = 1; i <= K; i++) choose[i] = mul(choose[i - 1], K - i + 1);
  dfs(1, 0);
  for (int i = 1; i <= N; i++) {
    add(ans, mul(down[i], down[i - 1]));
    add(down[i], down[i - 1]);
  }
  return ans;
}
int main() {
  load();
  printf("%d\n", solve());
  return 0;
}