Problem: The Main Martian Tree grows on Mars. It is a binary tree (a rooted tree, with no more than two sons at each vertex) with n vertices, where the root vertex has the number 1. Its fruits are the Main Martian Fruits. It's summer now, so this tree does not have any fruit yet.

Autumn is coming soon, and leaves and branches will begin to fall off the tree. It is clear, that if a vertex falls off the tree, then its entire subtree will fall off too. In addition, the root will remain on the tree. Formally: the tree will have some connected subset of vertices containing the root.

After that, the fruits will grow on the tree (only at those vertices which remain). Exactly x fruits will grow in the root. The number of fruits in each remaining vertex will be not less than the sum of the numbers of fruits in the remaining sons of this vertex. It is allowed, that some vertices will not have any fruits.

Natasha wondered how many tree configurations can be after the described changes. Since this number can be very large, output it modulo 998244353.

Two configurations of the resulting tree are considered different if one of these two conditions is true:

  * they have different subsets of remaining vertices;
  * they have the same subset of remaining vertices, but there is a vertex in this subset where they have a different amount of fruits.

Input

The first line contains two integers: n and x (1 ≤ n ≤ 10^5, 0 ≤ x ≤ 10^{18}) — the size of the tree and the number of fruits in the root.

The i-th of the following (n-1) lines contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ n) — vertices connected by the i-th edge of the tree.

It is guaranteed that the input data describes a correct binary tree with the root at the vertex 1.

Output

Print one number — the number of configurations of the resulting tree modulo 998244353.

Examples

Input

3 2
1 2
1 3


Output

13


Input

2 5
1 2


Output

7


Input

4 10
1 2
1 3
3 4


Output

441

Note

Consider the first example. <image>

There are 2 fruits at the vertex 1. The following 13 options are possible:

  * there is no vertex 2, there is no vertex 3; <image>
  * there is no vertex 2, there are no fruits at the vertex 3; <image>
  * there is no vertex 2, there is 1 fruit at the vertex 3; <image>
  * there is no vertex 2, there are 2 fruits at the vertex 3; <image>
  * there are no fruits at the vertex 2, there is no vertex 3; <image>
  * there are no fruits at the vertex 2, there are no fruits at the vertex 3; <image>
  * there are no fruits at the vertex 2, there is 1 fruit at the vertex 3; <image>
  * there are no fruits at the vertex 2, there are 2 fruits at the vertex 3; <image>
  * there is 1 fruit at the vertex 2, there is no vertex 3; <image>
  * there is 1 fruit at the vertex 2, there are no fruits at the vertex 3; <image>
  * there is 1 fruit at the vertex 2, there is 1 fruit at the vertex 3; <image>
  * there are 2 fruits at the vertex 2, there is no vertex 3; <image>
  * there are 2 fruits at the vertex 2, there are no fruits at the vertex 3. <image>



Consider the second example. There are 5 fruits at the vertex 1. The following 7 options are possible:

  * there is no vertex 2;
  * there are no fruits at the vertex 2;
  * there is 1 fruit at the vertex 2;
  * there are 2 fruits at the vertex 2;
  * there are 3 fruits at the vertex 2;
  * there are 4 fruits at the vertex 2;
  * there are 5 fruits at the vertex 2.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using std::max;
using std::min;
const int inf = 0x3f3f3f3f, Inf = 0x7fffffff;
const long long INF = 0x3f3f3f3f3f3f3f3f;
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
template <typename _Tp>
_Tp gcd(const _Tp &a, const _Tp &b) {
  return !b ? a : gcd(b, a % b);
}
template <typename _Tp>
inline _Tp abs(const _Tp &a) {
  return a >= 0 ? a : -a;
}
template <typename _Tp>
inline void chmax(_Tp &a, const _Tp &b) {
  a = a < b ? b : a;
}
template <typename _Tp>
inline void chmin(_Tp &a, const _Tp &b) {
  a = a < b ? a : b;
}
template <typename _Tp>
inline void read(_Tp &x) {
  char ch(getchar());
  bool f(false);
  while (!isdigit(ch)) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (isdigit(ch)) x = (((x << 2) + x) << 1) + (ch & 15), ch = getchar();
  f && (x = -x);
}
template <typename _Tp, typename... Args>
void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
inline int read_str(char *s) {
  char ch(getchar());
  while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
  char *tar = s;
  *tar++ = ch, ch = getchar();
  while (ch != ' ' && ch != '\r' && ch != '\n' && ch != EOF)
    *tar++ = ch, ch = getchar();
  return *tar = 0, tar - s;
}
const int max_len = 1 << 18, N = max_len + 5, mod = 998244353;
template <typename _Tp1, typename _Tp2>
inline void add(_Tp1 &a, _Tp2 b) {
  (a += b) >= mod && (a -= mod);
}
template <typename _Tp1, typename _Tp2>
inline void sub(_Tp1 &a, _Tp2 b) {
  (a -= b) < 0 && (a += mod);
}
template <typename _Tp>
inline _Tp _sub(_Tp a, const _Tp &b) {
  (a += mod - b) >= mod && (a -= mod);
  return a;
}
long long ksm(long long a, long long b = mod - 2) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod, b >>= 1;
  }
  return res;
}
void print(const std::vector<int> &a) {
  for (auto it : a) printf("%d ", it);
  printf("\n");
}
std::vector<int> operator<<(const std::vector<int> &a, unsigned int b) {
  std::vector<int> o(a.size() + b);
  for (unsigned int i = 0; i < b; ++i) o[i] = 0;
  for (unsigned int i = 0; i < a.size(); ++i) o[i + b] = a[i];
  return o;
}
inline std::vector<int> operator<<=(std::vector<int> &a, unsigned int b) {
  return a = a << b;
}
inline std::vector<int> operator>>(const std::vector<int> &a, unsigned int b) {
  return b >= a.size() ? std::vector<int>()
                       : std::vector<int>{a.begin() + b, a.end()};
}
inline std::vector<int> operator>>=(std::vector<int> &a, unsigned int b) {
  return a = b >= a.size() ? std::vector<int>()
                           : std::vector<int>{a.begin() + b, a.end()};
}
std::vector<int> operator+=(std::vector<int> &a, const std::vector<int> &b) {
  if (((int)b.size()) > ((int)a.size())) a.resize(((int)b.size()));
  for (unsigned int i = 0; i < b.size(); ++i) add(a[i], b[i]);
  return a;
}
inline std::vector<int> operator+(const std::vector<int> &a,
                                  const std::vector<int> &b) {
  std::vector<int> tmp(a);
  tmp += b;
  return tmp;
}
std::vector<int> operator-=(std::vector<int> &a, const std::vector<int> &b) {
  if (((int)b.size()) > ((int)a.size())) a.resize(((int)b.size()));
  for (unsigned int i = 0; i < b.size(); ++i) sub(a[i], b[i]);
  return a;
}
inline std::vector<int> operator-(const std::vector<int> &a,
                                  const std::vector<int> &b) {
  std::vector<int> tmp(a);
  tmp -= b;
  return tmp;
}
unsigned long long Omgs[N];
int r[N];
const unsigned long long Omg = ksm(3, (mod - 1) / max_len);
int getlen(int len) {
  int limit = 1;
  while (limit < len) limit <<= 1;
  for (int i = 0; i < limit; ++i)
    r[i] = (r[i >> 1] >> 1) | (i & 1 ? limit >> 1 : 0);
  return limit;
}
void setup() {
  Omgs[max_len >> 1] = 1;
  for (int i = (max_len >> 1) + 1; i < max_len; ++i)
    Omgs[i] = Omgs[i - 1] * Omg % mod;
  for (int i = (max_len >> 1) - 1; i > 0; --i) Omgs[i] = Omgs[i << 1];
}
void dft(unsigned long long *A, int limit) {
  for (int i = 0; i < limit; ++i)
    if (i < r[i]) std::swap(A[i], A[r[i]]);
  for (int len = 1; len < limit; len <<= 1) {
    if (len == 262144)
      for (int i = 0; i < limit; ++i) A[i] %= mod;
    for (int i = 0; i < limit; i += len << 1) {
      unsigned long long *p = A + i, *q = A + i + len, *w = Omgs + len;
      for (int _ = 0; _ < len; ++_, ++p, ++q, ++w) {
        unsigned long long tmp = *q * *w % mod;
        *q = *p + mod - tmp, *p += tmp;
      }
    }
  }
  for (int i = 0; i < limit; ++i) A[i] %= mod;
}
void idft(unsigned long long *A, int limit) {
  std::reverse(A + 1, A + limit), dft(A, limit);
  unsigned long long inv = mod - (mod - 1) / limit;
  for (int i = 0; i < limit; ++i) A[i] = inv * A[i] % mod;
}
unsigned long long _f[N], _g[N];
std::vector<int> operator*(const std::vector<int> &a,
                           const std::vector<int> &b) {
  unsigned int len = a.size() + b.size() - 1;
  if (a.size() <= 64u || b.size() <= 64u) {
    std::vector<int> c(len);
    for (unsigned int i = 0; i < a.size(); ++i)
      for (unsigned int j = 0; j < b.size(); ++j)
        add(c[i + j], 1ull * a[i] * b[j] % mod);
    return c;
  }
  int limit = getlen(len);
  memset(_f, 0, limit << 3);
  for (unsigned int i = 0; i < a.size(); ++i) _f[i] = a[i];
  memset(_g, 0, limit << 3);
  for (unsigned int i = 0; i < b.size(); ++i) _g[i] = b[i];
  dft(_f, limit), dft(_g, limit);
  for (int i = 0; i < limit; ++i) _f[i] = 1ULL * _f[i] * _g[i] % mod;
  idft(_f, limit);
  std::vector<int> ans(len);
  for (unsigned int i = 0; i < len; ++i) ans[i] = _f[i];
  return ans;
}
std::vector<int> mul(const std::vector<int> &a, const std::vector<int> &b,
                     unsigned int len, bool need = true) {
  if (a.size() <= 64u || b.size() <= 64u) {
    std::vector<int> c(((int)a.size()) + ((int)b.size()) - 1);
    for (unsigned int i = 0; i < a.size(); ++i)
      for (unsigned int j = 0; j < b.size(); ++j)
        add(c[i + j], 1ull * a[i] * b[j] % mod);
    return c.resize(len), c;
  }
  int limit = getlen(len);
  memset(_f, 0, limit << 3);
  for (unsigned int i = 0; i < a.size(); ++i) _f[i] = a[i];
  dft(_f, limit);
  if (need) {
    memset(_g, 0, limit << 3);
    for (unsigned int i = 0; i < b.size(); ++i) _g[i] = b[i];
    dft(_g, limit);
  }
  for (int i = 0; i < limit; ++i) _f[i] = 1ULL * _f[i] * _g[i] % mod;
  idft(_f, limit);
  std::vector<int> ans(len);
  for (unsigned int i = 0; i < len; ++i) ans[i] = _f[i];
  return ans;
}
inline std::vector<int> operator*=(std::vector<int> &a,
                                   const std::vector<int> &b) {
  return a = a * b;
}
template <typename _Tp>
inline std::vector<int> operator*=(std::vector<int> &a, const _Tp &b) {
  for (auto &&it : a) it = 1ll * it * b % mod;
  return a;
}
template <typename _Tp>
inline std::vector<int> operator*(std::vector<int> a, const _Tp &b) {
  return a *= b;
}
template <typename _Tp>
inline std::vector<int> operator*(const _Tp &b, std::vector<int> a) {
  return a *= b;
}
template <typename _Tp>
inline std::vector<int> operator/=(std::vector<int> &a, const _Tp &b) {
  unsigned long long inv = ksm(b);
  for (auto &&it : a) it = 1ll * it * inv % mod;
  return a;
}
template <typename _Tp>
inline std::vector<int> operator/(std::vector<int> a, const _Tp &b) {
  return a /= b;
}
template <typename _Tp>
inline std::vector<int> operator/(const _Tp &b, std::vector<int> a) {
  return a /= b;
}
struct edge {
  int v, nxt;
} c[N << 1];
int front[N], edge_cnt;
inline void addedge(int u, int v) {
  c[++edge_cnt] = (edge){v, front[u]}, front[u] = edge_cnt;
}
int son[N], siz[N], lson[N];
void dfs1(int x, int fa) {
  siz[x] = 1;
  for (int i = front[x]; i; i = c[i].nxt) {
    int v = c[i].v;
    if (v == fa) continue;
    dfs1(v, x), siz[x] += siz[v];
    if (siz[v] > siz[son[x]])
      lson[x] = son[x], son[x] = v;
    else
      lson[x] = v;
  }
}
std::vector<std::vector<int> > _;
std::pair<std::vector<int>, std::vector<int> > solve(int l, int r) {
  if (l == r) return {_[l], _[l]};
  int mid = (l + r) >> 1;
  auto [fl, gl] = solve(l, mid);
  auto [fr, gr] = solve(mid + 1, r);
  return {fl * fr, gl * fr + gr};
}
std::vector<int> dfs2(int x) {
  if (!x) return {1};
  std::vector<int> nd;
  int cur = x;
  while (cur) nd.push_back(cur), cur = son[cur];
  std::vector<std::vector<int> > a;
  for (auto it : nd) a.push_back(dfs2(lson[it]) << 1);
  std::reverse(a.begin(), a.end());
  return _ = a, solve(0, ((int)_.size()) - 1).second + std::vector<int>{1};
}
long long inv[N];
int main() {
  inv[0] = inv[1] = 1;
  for (int i = 2; i < N; ++i) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
  setup();
  int n;
  long long X;
  read(n, X), X %= mod;
  int x, y;
  for (int i = 1; i < n; ++i) read(x, y), addedge(x, y), addedge(y, x);
  dfs1(1, 0);
  std::vector<int> ans(dfs2(1));
  long long cur = 1, res = 0;
  for (int i = 1; i <= n; ++i) {
    if (i > 1) cur = cur * (i + X - 1) % mod * inv[i - 1] % mod;
    add(res, cur * ans[i] % mod);
  }
  printf("%lld\n", res);
  return 0;
}