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>
#pragma GCC optimize("O3")
using namespace std;
mt19937 rnd(239);
const long double pi = acos(-1.0);
const long long INF = 1e18 + 239;
const int BIG = 1e9 + 239;
const int M = 2e5 + 239;
const int T = (1 << 19);
const long long MOD = 998244353;
const long long root = 3;
const long long sub = 15311432;
long long st[T];
inline long long power(long long a, long long b) {
  if (b == 0) return 1;
  long long t = power(a, (b >> 1));
  t = (t * t) % MOD;
  if (b & 1) return (t * a) % MOD;
  return t;
}
inline int inv(int n, int b) {
  int ans = 0;
  for (int i = 0; i < b; i++) {
    ans = (ans << 1) + (n & 1);
    n >>= 1;
  }
  return ans;
}
int p;
long long w;
map<vector<long long>, vector<long long> > pq;
inline void fft(const vector<long long> &a, vector<long long> &b) {
  if (pq.count(a)) {
    b = pq[a];
    return;
  }
  b.resize(a.size());
  for (int i = 0; i < a.size(); i++) b[i] = a[inv(i, p)];
  for (int z = 0; z < p; z++) {
    int u = (1 << z);
    for (int i = 0; i < (1 << p); i++) {
      int ps = i >> z;
      if ((ps & 1) == 0) {
        int t = i & (u - 1);
        long long bi = (b[i] + st[t << (p - z - 1)] * b[i + u]) % MOD;
        long long bii = (b[i] + st[(t + u) << (p - z - 1)] * b[i + u]) % MOD;
        b[i] = bi;
        b[i + u] = bii;
      }
    }
  }
  pq[a] = b;
}
inline vector<long long> sum(vector<long long> a, vector<long long> b) {
  int n = max((int)a.size(), (int)b.size());
  vector<long long> ans(n, 0);
  while (a.size() < n) a.push_back(0);
  while (b.size() < n) b.push_back(0);
  for (int i = 0; i < n; i++) ans[i] = (a[i] + b[i]) % MOD;
  return ans;
}
vector<long long> ta, tb;
vector<long long> as;
inline vector<long long> multiply(vector<long long> a, vector<long long> b) {
  int k = (a.size() + b.size() + 1);
  p = trunc(log2(k)) + 1;
  while (a.size() < (1 << p)) a.push_back(0);
  while (b.size() < (1 << p)) b.push_back(0);
  w = power(sub, (1 << (23 - p)));
  st[0] = 1LL;
  for (int i = 1; i < (1 << p); i++) st[i] = (st[i - 1] * w) % MOD;
  fft(a, ta);
  fft(b, tb);
  vector<long long> v;
  for (int i = 0; i < (1 << p); i++) v.push_back((ta[i] * tb[i]) % MOD);
  fft(v, as);
  long long d = power((1 << p), MOD - 2);
  for (int i = 0; i < (1 << p); i++) as[i] = (d * as[i]) % MOD;
  reverse(as.begin() + 1, as.end());
  while (as.back() == 0) as.pop_back();
  return as;
}
int n, k, kol[M];
vector<int> v[M];
long long f[M], ans;
long long mlt;
int sz;
long long a[M], s[M];
long long u, kf[M], fact[M];
inline pair<vector<long long>, vector<long long> > func(int l, int r) {
  if (r - l == 1) return {{s[l], (u * s[l]) % MOD}, {1, a[l]}};
  int mid = (l + r) >> 1;
  pair<vector<long long>, vector<long long> > a1 = func(l, mid);
  pair<vector<long long>, vector<long long> > a2 = func(mid, r);
  return make_pair(
      sum(multiply(a1.first, a2.second), multiply(a1.second, a2.first)),
      multiply(a1.second, a2.second));
}
long long dfs(int p, int pr) {
  kol[p] = 1;
  int szt = 0;
  vector<long long> aa, sa;
  for (int i : v[p])
    if (pr != i) {
      long long now = dfs(i, p);
      kol[p] += kol[i];
      aa.push_back(kol[i]);
      sa.push_back(now);
    }
  sz = aa.size();
  for (int i = 0; i < sz; i++) {
    a[i] = aa[i];
    s[i] = sa[i];
  }
  u = n - kol[p];
  long long sum = 0;
  for (int i = 0; i < sz; i++) sum = (sum + s[i]) % MOD;
  long long sqr = 0;
  for (int i = 0; i < sz; i++) sqr = (sqr + s[i] * s[i]) % MOD;
  sqr = (sum * sum - sqr) % MOD;
  if (sqr < 0) sqr += MOD;
  ans = (ans + sqr * mlt) % MOD;
  if (sz == 0) {
    return 1;
  }
  pair<vector<long long>, vector<long long> > t = func(0, sz);
  int s = (int)t.first.size();
  for (int i = 0; i < min(s, k + 1); i++) {
    ans = (ans + kf[i] * t.first[i]) % MOD;
    sum = (sum + kf[i] * t.second[i]) % MOD;
  }
  return sum;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  if (k == 1) {
    cout << (((long long)n * (long long)(n - 1)) / 2) % MOD;
    return 0;
  }
  for (int i = 0; i < n - 1; i++) {
    int s, f;
    cin >> s >> f;
    s--, f--;
    v[s].push_back(f);
    v[f].push_back(s);
  }
  fact[0] = 1;
  for (int i = 0; i < k; i++)
    fact[i + 1] = (fact[i] * (long long)(i + 1)) % MOD;
  for (int i = 0; i <= k; i++)
    kf[i] = (fact[k] * power(fact[k - i], MOD - 2)) % MOD;
  ans = 0;
  mlt = power(2, MOD - 2);
  dfs(0, -1);
  cout << ans;
  return 0;
}