#include <bits/stdc++.h>
using namespace std;
struct InputReader {
  char buf[1048576];
  int p;
  inline InputReader() { p = 1048576; }
  inline void Flush() {
    p = 0;
    fread(buf, 1, 1048576, stdin);
  }
  inline char C() {
    if (p >= 1048576) Flush();
    return buf[p++];
  }
  inline char Readnum() {
    char ch = C();
    while (!isdigit(ch) && ch != '-') ch = C();
    return ch;
  }
  inline void Readalpha(char &c) {
    c = C();
    while (!isalpha(c)) c = C();
  }
  int operator()() {
    int ans = 0, fu = 1;
    char ch = Readnum();
    if (ch == '-') fu = -1, ch = C();
    while (ch >= '0' && ch <= '9') {
      ans = ans * 10 + ch - '0';
      ch = C();
    }
    return ans * fu;
  }
  long long Readll() {
    long long ans = 0LL, fu = 1LL;
    char ch = Readnum();
    if (ch == '-') fu = -1LL, ch = C();
    while (ch >= '0' && ch <= '9') {
      ans = ans * 10LL + ch - '0';
      ch = C();
    }
    return ans * fu;
  }
  inline void Readstring(string &x) {
    x.clear();
    char ch = C();
    while (!isdigit(ch) && !isalpha(ch) && ch != '#' && ch != '.') ch = C();
    while (isdigit(ch) || isalpha(ch) || ch == '#' || ch == '.') {
      x += ch;
      ch = C();
    }
  }
  inline void Readchstring(char s[]) {
    int len = 0;
    char ch = C();
    while (!isdigit(ch) && !isalpha(ch)) ch = C();
    while (isdigit(ch) || isalpha(ch)) {
      s[len++] = ch;
      ch = C();
    }
    s[len] = '\0';
  }
  inline void Specialread(char &c) {
    c = C();
    while (!isdigit(c) && !isalpha(c) && c != '#' && c != '.' && c != '=' &&
           c != 'B')
      c = C();
  }
} In;
inline void Read(int &x) { x = In(); }
inline void Read(int &x, int &y) {
  x = In();
  y = In();
}
inline void Read(int &x1, int &x2, int &x3) {
  x1 = In();
  x2 = In();
  x3 = In();
}
inline void Read(int &x1, int &x2, int &x3, int &x4) {
  x1 = In();
  x2 = In();
  x3 = In();
  x4 = In();
}
inline void Read(long long &x) { x = In.Readll(); }
inline void Read(long long &x, long long &y) {
  x = In.Readll();
  y = In.Readll();
}
inline void Read(long long &x1, long long &x2, long long &x3) {
  x1 = In.Readll();
  x2 = In.Readll();
  x3 = In.Readll();
}
inline void Read(long long &x1, long long &x2, long long &x3, long long &x4) {
  x1 = In.Readll();
  x2 = In.Readll();
  x3 = In.Readll();
  x4 = In.Readll();
}
template <typename T>
void Read(T a[], int st, int ed) {
  for (int(i) = (st); (i) <= (ed); ++(i)) Read(a[i]);
}
inline void FILEIO() {}
inline void FILEIO(string pname) {
  freopen((pname + ".in").c_str(), "r", stdin);
  freopen((pname + ".out").c_str(), "w", stdout);
}
inline void FILEIO_OICONTEST(string pname) {
  freopen((pname + ".in").c_str(), "r", stdin);
  freopen((pname + ".out").c_str(), "w", stdout);
}
void Printtime() {}
void END() {
  Printtime();
  exit(0);
}
template <typename T>
void END(T mes) {
  cout << mes << endl;
  END();
}
template <typename T>
void Print(T a[], int s, int t, char sp = ' ', char ed = '\n') {
  if (s > t) return;
  for (int i = s; i < t; i++) cout << a[i] << sp;
  cout << a[t] << ed;
  cout.flush();
}
template <typename T>
void Print(T a, int s = 0, int t = -1, char sp = ' ', char ed = '\n') {
  if (t == -1) t = a.size() - 1;
  for (int i = s; i <= t; i++) cout << a[i] << sp;
  cout << ed;
  cout.flush();
}
vector<int> Range(int l, int r) {
  vector<int> ret{};
  for (int(i) = (l); (i) <= (r); ++(i)) ret.push_back(i);
  return ret;
}
mt19937 Rand(0xe38195e38293);
template <typename T>
inline T Mymo(const T &x) {
  return x >= (998244353LL) ? x - (998244353LL) : x;
}
template <typename T>
inline void Mymod(T &x) {
  x = x >= (998244353LL) ? x - (998244353LL) : x;
}
template <typename T1, typename T2>
inline void Addi(T1 &x, const T2 &y) {
  x = Mymo(x + y);
}
template <typename T1, typename T2>
inline void Deci(T1 &x, const T2 &y) {
  x = Mymo(x - y + (998244353LL));
}
inline long long Pow(long long a, long long b,
                     const long long p = (998244353LL)) {
  long long ret = 1;
  for (; b; a = a * a % p, b >>= 1LL)
    if (b & 1LL) ret = ret * a % p;
  return ret;
}
inline long long Inv(long long a, const long long p = (998244353LL)) {
  return Pow(a, p - 2LL, p);
}
const long long inv3 = Inv(3);
const int MAXN = 262144;
inline void MultX(vector<long long> &a) { a.insert(a.begin(), 0); }
inline void RemoveZero(vector<long long> &a) {
  while (!a.empty() and !a.back()) a.pop_back();
}
long long w[MAXN], invw[MAXN];
void InitW() {
  const long long bs = Pow(3, 998244352 / MAXN), invbs = Inv(bs);
  long long tb = 1, invtb = 1;
  for (int(i) = 0; (i) < (MAXN); ++(i)) {
    w[i] = tb;
    (tb *= bs) %= (998244353LL);
    invw[i] = invtb;
    (invtb *= invbs) %= (998244353LL);
  }
}
void NTT(vector<long long> &a, int n, bool useinv = 0) {
  a.resize(n);
  int logn = 31 - __builtin_clz(n);
  for (int(i) = 0; (i) < (n); ++(i)) {
    int to = 0;
    for (int(j) = 0; (j) < (logn); ++(j)) to |= (i >> j & 1) << logn - j - 1;
    if (to < i) swap(a[to], a[i]);
  }
  auto uw = useinv ? invw : w;
  for (int len = 2; len <= n; len <<= 1) {
    int half = len >> 1, divres = MAXN / len;
    for (int(st) = (0); (st) <= (n - 1); (st) += (len))
      for (int(k) = 0; (k) < (half); ++(k)) {
        const long long l = a[st + k],
                        r = uw[divres * k] * a[st + k + half] % (998244353LL);
        a[st + k] = Mymo(l + r);
        a[st + k + half] = Mymo(l - r + (998244353LL));
      }
  }
  if (useinv) {
    const long long invn = Inv(n);
    for (int(i) = 0; (i) < (n); ++(i)) (a[i] *= invn) %= (998244353LL);
  }
}
inline vector<long long> PolyMul(vector<long long> a, vector<long long> b) {
  int len = 1;
  while (len < a.size() + b.size()) len <<= 1;
  NTT(a, len);
  NTT(b, len);
  for (int(i) = 0; (i) < (len); ++(i)) a[i] = a[i] * b[i] % (998244353LL);
  NTT(a, len, 1);
  RemoveZero(a);
  return a;
}
inline vector<long long> operator+(const vector<long long> &a,
                                   const vector<long long> &b) {
  int sz = max(a.size(), b.size());
  vector<long long> res(sz);
  for (int(i) = 0; (i) < (sz); ++(i))
    res[i] = Mymo((i >= a.size() ? 0 : a[i]) + (i >= b.size() ? 0 : b[i]));
  return res;
}
inline void operator+=(vector<long long> &a, const vector<long long> &b) {
  int sz = max(a.size(), b.size());
  a.resize(sz);
  for (int(i) = 0; (i) < (sz); ++(i))
    a[i] = i >= b.size() ? a[i] : Mymo(a[i] + b[i]);
}
int n;
long long x;
vector<int> e[MAXN];
int sz[MAXN], gson[MAXN];
void FindGson(int pos, int fa) {
  sz[pos] = 1;
  for (auto v : e[pos]) {
    if (v == fa) continue;
    FindGson(v, pos);
    sz[pos] += sz[v];
    if (sz[v] > sz[gson[pos]]) {
      gson[pos] = v;
    }
  }
}
int top[MAXN], bottom[MAXN];
vector<int> glinks[MAXN];
void LinkLine(int pos, int fa, int tp) {
  top[pos] = tp;
  glinks[top[pos]].emplace_back(pos);
  bottom[tp] = pos;
  if (gson[pos]) LinkLine(gson[pos], pos, tp);
  for (auto v : e[pos]) {
    if (v == fa or v == gson[pos]) continue;
    LinkLine(v, pos, v);
  }
}
vector<long long> poly[MAXN];
vector<long long> light[MAXN];
pair<vector<long long>, vector<long long>> DC(const vector<int> &ps, int l,
                                              int r) {
  if (l == r) {
    int p = ps[l];
    return {light[p], light[p]};
  }
  int mid = l + r >> 1;
  auto lres = DC(ps, l, mid);
  auto rres = DC(ps, mid + 1, r);
  return {PolyMul(lres.first, rres.first),
          lres.second + PolyMul(lres.first, rres.second)};
}
void Solve(int pos, int fa) {
  bool istop = top[pos] == pos;
  light[pos] = {1};
  for (auto v : e[pos]) {
    if (v == fa or v == gson[pos]) continue;
    Solve(v, pos);
    light[pos] = PolyMul(light[pos], poly[v]);
  }
  MultX(light[pos]);
  if (gson[pos]) {
    Solve(gson[pos], pos);
  }
  if (top[pos] != pos) {
  } else {
    poly[pos] = DC(glinks[pos], 0, glinks[pos].size() - 1).second;
    Addi(poly[pos][0], 1);
  }
}
long long GetFinalAns(const vector<long long> &poly) {
  long long ans = 0;
  long long c = 1;
  for (int(i) = 1; (i) <= (n); ++(i)) {
    Addi(ans, poly[i] * c % (998244353LL));
    c = c * ((x + i) % (998244353LL)) % (998244353LL) * Inv(i) % (998244353LL);
  }
  return ans;
}
int main() {
  FILEIO();
  InitW();
  Read(n);
  Read(x);
  for (int(i) = 1; (i) <= (n - 1); ++(i)) {
    int a;
    Read(a);
    ;
    int b;
    Read(b);
    ;
    ;
    e[a].push_back(b);
    e[b].push_back(a);
  }
  FindGson(1, 0);
  LinkLine(1, 0, 1);
  Solve(1, 0);
  long long ans = GetFinalAns(poly[1]);
  cout << ans << endl;
  END();
}

### Prompt

Please create a solution in Cpp to the following 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct InputReader {
  char buf[1048576];
  int p;
  inline InputReader() { p = 1048576; }
  inline void Flush() {
    p = 0;
    fread(buf, 1, 1048576, stdin);
  }
  inline char C() {
    if (p >= 1048576) Flush();
    return buf[p++];
  }
  inline char Readnum() {
    char ch = C();
    while (!isdigit(ch) && ch != '-') ch = C();
    return ch;
  }
  inline void Readalpha(char &c) {
    c = C();
    while (!isalpha(c)) c = C();
  }
  int operator()() {
    int ans = 0, fu = 1;
    char ch = Readnum();
    if (ch == '-') fu = -1, ch = C();
    while (ch >= '0' && ch <= '9') {
      ans = ans * 10 + ch - '0';
      ch = C();
    }
    return ans * fu;
  }
  long long Readll() {
    long long ans = 0LL, fu = 1LL;
    char ch = Readnum();
    if (ch == '-') fu = -1LL, ch = C();
    while (ch >= '0' && ch <= '9') {
      ans = ans * 10LL + ch - '0';
      ch = C();
    }
    return ans * fu;
  }
  inline void Readstring(string &x) {
    x.clear();
    char ch = C();
    while (!isdigit(ch) && !isalpha(ch) && ch != '#' && ch != '.') ch = C();
    while (isdigit(ch) || isalpha(ch) || ch == '#' || ch == '.') {
      x += ch;
      ch = C();
    }
  }
  inline void Readchstring(char s[]) {
    int len = 0;
    char ch = C();
    while (!isdigit(ch) && !isalpha(ch)) ch = C();
    while (isdigit(ch) || isalpha(ch)) {
      s[len++] = ch;
      ch = C();
    }
    s[len] = '\0';
  }
  inline void Specialread(char &c) {
    c = C();
    while (!isdigit(c) && !isalpha(c) && c != '#' && c != '.' && c != '=' &&
           c != 'B')
      c = C();
  }
} In;
inline void Read(int &x) { x = In(); }
inline void Read(int &x, int &y) {
  x = In();
  y = In();
}
inline void Read(int &x1, int &x2, int &x3) {
  x1 = In();
  x2 = In();
  x3 = In();
}
inline void Read(int &x1, int &x2, int &x3, int &x4) {
  x1 = In();
  x2 = In();
  x3 = In();
  x4 = In();
}
inline void Read(long long &x) { x = In.Readll(); }
inline void Read(long long &x, long long &y) {
  x = In.Readll();
  y = In.Readll();
}
inline void Read(long long &x1, long long &x2, long long &x3) {
  x1 = In.Readll();
  x2 = In.Readll();
  x3 = In.Readll();
}
inline void Read(long long &x1, long long &x2, long long &x3, long long &x4) {
  x1 = In.Readll();
  x2 = In.Readll();
  x3 = In.Readll();
  x4 = In.Readll();
}
template <typename T>
void Read(T a[], int st, int ed) {
  for (int(i) = (st); (i) <= (ed); ++(i)) Read(a[i]);
}
inline void FILEIO() {}
inline void FILEIO(string pname) {
  freopen((pname + ".in").c_str(), "r", stdin);
  freopen((pname + ".out").c_str(), "w", stdout);
}
inline void FILEIO_OICONTEST(string pname) {
  freopen((pname + ".in").c_str(), "r", stdin);
  freopen((pname + ".out").c_str(), "w", stdout);
}
void Printtime() {}
void END() {
  Printtime();
  exit(0);
}
template <typename T>
void END(T mes) {
  cout << mes << endl;
  END();
}
template <typename T>
void Print(T a[], int s, int t, char sp = ' ', char ed = '\n') {
  if (s > t) return;
  for (int i = s; i < t; i++) cout << a[i] << sp;
  cout << a[t] << ed;
  cout.flush();
}
template <typename T>
void Print(T a, int s = 0, int t = -1, char sp = ' ', char ed = '\n') {
  if (t == -1) t = a.size() - 1;
  for (int i = s; i <= t; i++) cout << a[i] << sp;
  cout << ed;
  cout.flush();
}
vector<int> Range(int l, int r) {
  vector<int> ret{};
  for (int(i) = (l); (i) <= (r); ++(i)) ret.push_back(i);
  return ret;
}
mt19937 Rand(0xe38195e38293);
template <typename T>
inline T Mymo(const T &x) {
  return x >= (998244353LL) ? x - (998244353LL) : x;
}
template <typename T>
inline void Mymod(T &x) {
  x = x >= (998244353LL) ? x - (998244353LL) : x;
}
template <typename T1, typename T2>
inline void Addi(T1 &x, const T2 &y) {
  x = Mymo(x + y);
}
template <typename T1, typename T2>
inline void Deci(T1 &x, const T2 &y) {
  x = Mymo(x - y + (998244353LL));
}
inline long long Pow(long long a, long long b,
                     const long long p = (998244353LL)) {
  long long ret = 1;
  for (; b; a = a * a % p, b >>= 1LL)
    if (b & 1LL) ret = ret * a % p;
  return ret;
}
inline long long Inv(long long a, const long long p = (998244353LL)) {
  return Pow(a, p - 2LL, p);
}
const long long inv3 = Inv(3);
const int MAXN = 262144;
inline void MultX(vector<long long> &a) { a.insert(a.begin(), 0); }
inline void RemoveZero(vector<long long> &a) {
  while (!a.empty() and !a.back()) a.pop_back();
}
long long w[MAXN], invw[MAXN];
void InitW() {
  const long long bs = Pow(3, 998244352 / MAXN), invbs = Inv(bs);
  long long tb = 1, invtb = 1;
  for (int(i) = 0; (i) < (MAXN); ++(i)) {
    w[i] = tb;
    (tb *= bs) %= (998244353LL);
    invw[i] = invtb;
    (invtb *= invbs) %= (998244353LL);
  }
}
void NTT(vector<long long> &a, int n, bool useinv = 0) {
  a.resize(n);
  int logn = 31 - __builtin_clz(n);
  for (int(i) = 0; (i) < (n); ++(i)) {
    int to = 0;
    for (int(j) = 0; (j) < (logn); ++(j)) to |= (i >> j & 1) << logn - j - 1;
    if (to < i) swap(a[to], a[i]);
  }
  auto uw = useinv ? invw : w;
  for (int len = 2; len <= n; len <<= 1) {
    int half = len >> 1, divres = MAXN / len;
    for (int(st) = (0); (st) <= (n - 1); (st) += (len))
      for (int(k) = 0; (k) < (half); ++(k)) {
        const long long l = a[st + k],
                        r = uw[divres * k] * a[st + k + half] % (998244353LL);
        a[st + k] = Mymo(l + r);
        a[st + k + half] = Mymo(l - r + (998244353LL));
      }
  }
  if (useinv) {
    const long long invn = Inv(n);
    for (int(i) = 0; (i) < (n); ++(i)) (a[i] *= invn) %= (998244353LL);
  }
}
inline vector<long long> PolyMul(vector<long long> a, vector<long long> b) {
  int len = 1;
  while (len < a.size() + b.size()) len <<= 1;
  NTT(a, len);
  NTT(b, len);
  for (int(i) = 0; (i) < (len); ++(i)) a[i] = a[i] * b[i] % (998244353LL);
  NTT(a, len, 1);
  RemoveZero(a);
  return a;
}
inline vector<long long> operator+(const vector<long long> &a,
                                   const vector<long long> &b) {
  int sz = max(a.size(), b.size());
  vector<long long> res(sz);
  for (int(i) = 0; (i) < (sz); ++(i))
    res[i] = Mymo((i >= a.size() ? 0 : a[i]) + (i >= b.size() ? 0 : b[i]));
  return res;
}
inline void operator+=(vector<long long> &a, const vector<long long> &b) {
  int sz = max(a.size(), b.size());
  a.resize(sz);
  for (int(i) = 0; (i) < (sz); ++(i))
    a[i] = i >= b.size() ? a[i] : Mymo(a[i] + b[i]);
}
int n;
long long x;
vector<int> e[MAXN];
int sz[MAXN], gson[MAXN];
void FindGson(int pos, int fa) {
  sz[pos] = 1;
  for (auto v : e[pos]) {
    if (v == fa) continue;
    FindGson(v, pos);
    sz[pos] += sz[v];
    if (sz[v] > sz[gson[pos]]) {
      gson[pos] = v;
    }
  }
}
int top[MAXN], bottom[MAXN];
vector<int> glinks[MAXN];
void LinkLine(int pos, int fa, int tp) {
  top[pos] = tp;
  glinks[top[pos]].emplace_back(pos);
  bottom[tp] = pos;
  if (gson[pos]) LinkLine(gson[pos], pos, tp);
  for (auto v : e[pos]) {
    if (v == fa or v == gson[pos]) continue;
    LinkLine(v, pos, v);
  }
}
vector<long long> poly[MAXN];
vector<long long> light[MAXN];
pair<vector<long long>, vector<long long>> DC(const vector<int> &ps, int l,
                                              int r) {
  if (l == r) {
    int p = ps[l];
    return {light[p], light[p]};
  }
  int mid = l + r >> 1;
  auto lres = DC(ps, l, mid);
  auto rres = DC(ps, mid + 1, r);
  return {PolyMul(lres.first, rres.first),
          lres.second + PolyMul(lres.first, rres.second)};
}
void Solve(int pos, int fa) {
  bool istop = top[pos] == pos;
  light[pos] = {1};
  for (auto v : e[pos]) {
    if (v == fa or v == gson[pos]) continue;
    Solve(v, pos);
    light[pos] = PolyMul(light[pos], poly[v]);
  }
  MultX(light[pos]);
  if (gson[pos]) {
    Solve(gson[pos], pos);
  }
  if (top[pos] != pos) {
  } else {
    poly[pos] = DC(glinks[pos], 0, glinks[pos].size() - 1).second;
    Addi(poly[pos][0], 1);
  }
}
long long GetFinalAns(const vector<long long> &poly) {
  long long ans = 0;
  long long c = 1;
  for (int(i) = 1; (i) <= (n); ++(i)) {
    Addi(ans, poly[i] * c % (998244353LL));
    c = c * ((x + i) % (998244353LL)) % (998244353LL) * Inv(i) % (998244353LL);
  }
  return ans;
}
int main() {
  FILEIO();
  InitW();
  Read(n);
  Read(x);
  for (int(i) = 1; (i) <= (n - 1); ++(i)) {
    int a;
    Read(a);
    ;
    int b;
    Read(b);
    ;
    ;
    e[a].push_back(b);
    e[b].push_back(a);
  }
  FindGson(1, 0);
  LinkLine(1, 0, 1);
  Solve(1, 0);
  long long ans = GetFinalAns(poly[1]);
  cout << ans << endl;
  END();
}

```