#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() { return abs((int)mt()); }
struct NTT {
  static const int MAXF = 1 << 20;
  int pr;
  int rts[MAXF + 1];
  int bitrev[MAXF];
  int iv[MAXF + 1];
  int fpow(int a, int k, int p) {
    if (!k) return 1;
    int res = a, tmp = a;
    k--;
    while (k) {
      if (k & 1) {
        res = (long long)res * tmp % p;
      }
      tmp = (long long)tmp * tmp % p;
      k >>= 1;
    }
    return res;
  }
  void init(int pr, int pw) {
    this->pr = pr;
    int k = 0;
    while ((1 << k) < MAXF) k++;
    bitrev[0] = 0;
    for (int i = 1; i < MAXF; i++) {
      bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << k - 1);
    }
    pw = fpow(pw, (pr - 1) / MAXF, pr);
    rts[0] = 1;
    for (int i = 1; i <= MAXF; i++) {
      rts[i] = (long long)rts[i - 1] * pw % pr;
    }
    for (int i = 1; i <= MAXF; i <<= 1) {
      iv[i] = fpow(i, pr - 2, pr);
    }
  }
  void dft(int a[], int n, int sign) {
    int d = 0;
    while ((1 << d) * n != MAXF) d++;
    for (int i = 0; i < n; i++) {
      if (i < (bitrev[i] >> d)) {
        swap(a[i], a[bitrev[i] >> d]);
      }
    }
    for (int len = 2; len <= n; len <<= 1) {
      int delta = MAXF / len * sign;
      for (int i = 0; i < n; i += len) {
        int* w = sign > 0 ? rts : rts + MAXF;
        for (int k = 0; k + k < len; k++) {
          int &a1 = a[i + k + (len >> 1)], &a2 = a[i + k];
          int t = (long long)*w * a1 % pr;
          a1 = a2 - t;
          a2 = a2 + t;
          a1 += a1 < 0 ? pr : 0;
          a2 -= a2 >= pr ? pr : 0;
          w += delta;
        }
      }
    }
    if (sign < 0) {
      int in = iv[n];
      for (int i = 0; i < n; i++) {
        a[i] = (long long)a[i] * in % pr;
      }
    }
  }
  void multiply(int a[], int b[], int na, int nb, int c[]) {
    static int fa[MAXF], fb[MAXF];
    int n = na + nb - 1;
    while (n != (n & -n)) n += n & -n;
    for (int i = 0; i < n; i++) fa[i] = fb[i] = 0;
    for (int i = 0; i < na; i++) fa[i] = a[i];
    for (int i = 0; i < nb; i++) fb[i] = b[i];
    dft(fa, n, 1), dft(fb, n, 1);
    for (int i = 0; i < n; i++) fa[i] = (long long)fa[i] * fb[i] % pr;
    dft(fa, n, -1);
    for (int i = 0; i < n; i++) c[i] = fa[i];
  }
  vector<int> multiply(vector<int> a, vector<int> b) {
    static int fa[MAXF], fb[MAXF], fc[MAXF];
    int na = a.size(), nb = b.size();
    for (int i = 0; i < na; i++) fa[i] = a[i];
    for (int i = 0; i < nb; i++) fb[i] = b[i];
    multiply(fa, fb, na, nb, fc);
    int k = na + nb - 1;
    vector<int> res(k);
    for (int i = 0; i < k; i++) res[i] = fc[i];
    return res;
  }
} ntt;
const int maxn = 5e5 + 5;
int p2[maxn];
int pi2[maxn];
int n;
vector<int> adj[maxn];
int dp[maxn];
int res;
vector<int> divide(int l, int r, vector<int>& vals) {
  if (l == r) {
    vector<int> res(2);
    res[0] = (1 - vals[l] + MOD) % MOD;
    res[1] = vals[l];
    return res;
  }
  return ntt.multiply(divide(l, l + r >> 1, vals),
                      divide((l + r >> 1) + 1, r, vals));
}
void dfs(int u, int p) {
  vector<int> vals;
  int cnt = 0;
  for (int v : adj[u]) {
    if (v != p) {
      dfs(v, u);
      vals.push_back(dp[v]);
      cnt++;
    }
  }
  vector<int> f = int((vals).size()) ? divide(0, int((vals).size()) - 1, vals)
                                     : vector<int>(1);
  for (int i = (1); i < (int((vals).size()) + 1); ++i) {
    int num = (1 - pi2[i] + MOD) % MOD;
    addmod(dp[u], mult(num, f[i]));
  }
  addmod(res, dp[u]);
  dp[u] = (1 - dp[u] + MOD) % MOD;
}
void chemthan() {
  ntt.init(MOD, 3);
  for (int i = (0); i < (maxn); ++i) p2[i] = fpow(2, i);
  for (int i = (0); i < (maxn); ++i) pi2[i] = inv(p2[i]);
  cin >> n;
  for (int i = (0); i < (n - 1); ++i) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v), adj[v].push_back(u);
  }
  dfs(0, -1);
  cout << mult(p2[n], res) << "\n";
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

Let's define rank of undirected graph as rank of its adjacency matrix in R^{n × n}.

Given a tree. Each edge of this tree will be deleted with probability 1/2, all these deletions are independent. Let E be the expected rank of resulting forest. Find E ⋅ 2^{n-1} modulo 998244353 (it is easy to show that E ⋅ 2^{n-1} is an integer).

Input

First line of input contains n (1 ≤ n ≤ 5 ⋅ 10^{5}) — number of vertices.

Next n-1 lines contains two integers u v (1 ≤ u,    v ≤ n;    u ≠ v) — indices of vertices connected by edge.

It is guaranteed that given graph is a tree.

Output

Print one integer — answer to the problem.

Examples

Input

3
1 2
2 3


Output

6


Input

4
1 2
1 3
1 4


Output

14


Input

4
1 2
2 3
3 4


Output

18

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() { return abs((int)mt()); }
struct NTT {
  static const int MAXF = 1 << 20;
  int pr;
  int rts[MAXF + 1];
  int bitrev[MAXF];
  int iv[MAXF + 1];
  int fpow(int a, int k, int p) {
    if (!k) return 1;
    int res = a, tmp = a;
    k--;
    while (k) {
      if (k & 1) {
        res = (long long)res * tmp % p;
      }
      tmp = (long long)tmp * tmp % p;
      k >>= 1;
    }
    return res;
  }
  void init(int pr, int pw) {
    this->pr = pr;
    int k = 0;
    while ((1 << k) < MAXF) k++;
    bitrev[0] = 0;
    for (int i = 1; i < MAXF; i++) {
      bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << k - 1);
    }
    pw = fpow(pw, (pr - 1) / MAXF, pr);
    rts[0] = 1;
    for (int i = 1; i <= MAXF; i++) {
      rts[i] = (long long)rts[i - 1] * pw % pr;
    }
    for (int i = 1; i <= MAXF; i <<= 1) {
      iv[i] = fpow(i, pr - 2, pr);
    }
  }
  void dft(int a[], int n, int sign) {
    int d = 0;
    while ((1 << d) * n != MAXF) d++;
    for (int i = 0; i < n; i++) {
      if (i < (bitrev[i] >> d)) {
        swap(a[i], a[bitrev[i] >> d]);
      }
    }
    for (int len = 2; len <= n; len <<= 1) {
      int delta = MAXF / len * sign;
      for (int i = 0; i < n; i += len) {
        int* w = sign > 0 ? rts : rts + MAXF;
        for (int k = 0; k + k < len; k++) {
          int &a1 = a[i + k + (len >> 1)], &a2 = a[i + k];
          int t = (long long)*w * a1 % pr;
          a1 = a2 - t;
          a2 = a2 + t;
          a1 += a1 < 0 ? pr : 0;
          a2 -= a2 >= pr ? pr : 0;
          w += delta;
        }
      }
    }
    if (sign < 0) {
      int in = iv[n];
      for (int i = 0; i < n; i++) {
        a[i] = (long long)a[i] * in % pr;
      }
    }
  }
  void multiply(int a[], int b[], int na, int nb, int c[]) {
    static int fa[MAXF], fb[MAXF];
    int n = na + nb - 1;
    while (n != (n & -n)) n += n & -n;
    for (int i = 0; i < n; i++) fa[i] = fb[i] = 0;
    for (int i = 0; i < na; i++) fa[i] = a[i];
    for (int i = 0; i < nb; i++) fb[i] = b[i];
    dft(fa, n, 1), dft(fb, n, 1);
    for (int i = 0; i < n; i++) fa[i] = (long long)fa[i] * fb[i] % pr;
    dft(fa, n, -1);
    for (int i = 0; i < n; i++) c[i] = fa[i];
  }
  vector<int> multiply(vector<int> a, vector<int> b) {
    static int fa[MAXF], fb[MAXF], fc[MAXF];
    int na = a.size(), nb = b.size();
    for (int i = 0; i < na; i++) fa[i] = a[i];
    for (int i = 0; i < nb; i++) fb[i] = b[i];
    multiply(fa, fb, na, nb, fc);
    int k = na + nb - 1;
    vector<int> res(k);
    for (int i = 0; i < k; i++) res[i] = fc[i];
    return res;
  }
} ntt;
const int maxn = 5e5 + 5;
int p2[maxn];
int pi2[maxn];
int n;
vector<int> adj[maxn];
int dp[maxn];
int res;
vector<int> divide(int l, int r, vector<int>& vals) {
  if (l == r) {
    vector<int> res(2);
    res[0] = (1 - vals[l] + MOD) % MOD;
    res[1] = vals[l];
    return res;
  }
  return ntt.multiply(divide(l, l + r >> 1, vals),
                      divide((l + r >> 1) + 1, r, vals));
}
void dfs(int u, int p) {
  vector<int> vals;
  int cnt = 0;
  for (int v : adj[u]) {
    if (v != p) {
      dfs(v, u);
      vals.push_back(dp[v]);
      cnt++;
    }
  }
  vector<int> f = int((vals).size()) ? divide(0, int((vals).size()) - 1, vals)
                                     : vector<int>(1);
  for (int i = (1); i < (int((vals).size()) + 1); ++i) {
    int num = (1 - pi2[i] + MOD) % MOD;
    addmod(dp[u], mult(num, f[i]));
  }
  addmod(res, dp[u]);
  dp[u] = (1 - dp[u] + MOD) % MOD;
}
void chemthan() {
  ntt.init(MOD, 3);
  for (int i = (0); i < (maxn); ++i) p2[i] = fpow(2, i);
  for (int i = (0); i < (maxn); ++i) pi2[i] = inv(p2[i]);
  cin >> n;
  for (int i = (0); i < (n - 1); ++i) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v), adj[v].push_back(u);
  }
  dfs(0, -1);
  cout << mult(p2[n], res) << "\n";
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}

```