#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5;
std::vector<int> g[N];
int n;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll extgcd(ll a, ll b, ll &x, ll &y) {
  ll d;
  return b == 0 ? (x = 1, y = 0, a)
                : (d = extgcd(b, a % b, y, x), y -= a / b * x, d);
}
ll modinv(ll a, ll mod = (ll)1e9 + 7) {
  ll x, y;
  extgcd(a, mod, x, y);
  if (x < 0) x += mod;
  return x;
}
ll modpow(ll a, ll b, ll mod = (ll)1e9 + 7) {
  ll r = 1;
  a %= mod;
  while (b) {
    if (b & 1) r = r * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return r;
}
const ll mod = 998244353;
ll dp[N][2];
ll prob[N][2];
ll inv2 = modinv(2, mod);
void dfs(int i, int p) {
  ll sum = 0;
  ll sum0 = 0;
  ll t = 1;
  for (int j : g[i])
    if (j != p) {
      dfs(j, i);
      t = t * (1 - inv2 * prob[j][0] % mod) % mod;
      ll g = (dp[j][0] + dp[j][1]) % mod;
      sum0 += g * inv2 + inv2 * dp[j][1] % mod;
      sum0 %= mod;
      sum += g;
    }
  sum %= mod;
  prob[i][0] = t;
  prob[i][1] = (mod + 1 - t) % mod;
  dp[i][0] = sum0 * t;
  dp[i][1] = prob[i][1] + (sum - t * sum0 % mod);
}
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  dfs(0, -1);
  ll ans = dp[0][0] + dp[0][1];
  ans %= mod;
  ans *= modpow(2, n, mod);
  ans = (ans % mod + mod) % mod;
  cout << ans << endl;
  return 0;
}

### Prompt

Please formulate a cpp solution to the following problem:

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;
using ll = long long;
const int N = 5e5;
std::vector<int> g[N];
int n;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll extgcd(ll a, ll b, ll &x, ll &y) {
  ll d;
  return b == 0 ? (x = 1, y = 0, a)
                : (d = extgcd(b, a % b, y, x), y -= a / b * x, d);
}
ll modinv(ll a, ll mod = (ll)1e9 + 7) {
  ll x, y;
  extgcd(a, mod, x, y);
  if (x < 0) x += mod;
  return x;
}
ll modpow(ll a, ll b, ll mod = (ll)1e9 + 7) {
  ll r = 1;
  a %= mod;
  while (b) {
    if (b & 1) r = r * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return r;
}
const ll mod = 998244353;
ll dp[N][2];
ll prob[N][2];
ll inv2 = modinv(2, mod);
void dfs(int i, int p) {
  ll sum = 0;
  ll sum0 = 0;
  ll t = 1;
  for (int j : g[i])
    if (j != p) {
      dfs(j, i);
      t = t * (1 - inv2 * prob[j][0] % mod) % mod;
      ll g = (dp[j][0] + dp[j][1]) % mod;
      sum0 += g * inv2 + inv2 * dp[j][1] % mod;
      sum0 %= mod;
      sum += g;
    }
  sum %= mod;
  prob[i][0] = t;
  prob[i][1] = (mod + 1 - t) % mod;
  dp[i][0] = sum0 * t;
  dp[i][1] = prob[i][1] + (sum - t * sum0 % mod);
}
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  dfs(0, -1);
  ll ans = dp[0][0] + dp[0][1];
  ans %= mod;
  ans *= modpow(2, n, mod);
  ans = (ans % mod + mod) % mod;
  cout << ans << endl;
  return 0;
}

```