#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

const int N = 200000;
int ans=0;
int a[N+10]; // read
int p[N+10]; // 当前每个节点对应st节点下标 pos[u]
vector<int> e[N+10]; // edge
set<int> st[N+10]; // st[顶点] = {链到根的xor集合}

void dfs(int u,int f, int x) {
  int &iu = p[u]; // 真的u
  int bu = x^a[u]; // 从根下来的xor 链
  st[iu].insert(bu);
  bool delu = false; // delete u
  for(auto v:e[u]) if(v != f){
    dfs(v,u,bu);
    int &iv = p[v];
    // 把小的向大的合并, 结果存在st[iu] 中
    if(st[iu].size() < st[iv].size()) swap(iu, iv);
    for(auto val:st[iv]){
      if(delu) break;
      if(st[iu].count(val ^ a[u])) delu = true;
    }
    if(!delu) for(auto val:st[iv]) st[iu].insert(val);
    st[iv] = {};
  }
  if(delu){
    st[iu] = {};
    ans++;
  }
}

int main() {
  int n = read();
  rep(i,1,n+1) {
    a[i] = read();
    p[i] = i;
  }
  rep(i,1,n){
    int u = read();
    int v = read();
    e[u].pb(v);
    e[v].pb(u);
  }
  dfs(1,0,0);
  printf("%d\n",ans);
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

// ------------------------------- NTT --------------------------------
namespace NTT998{
  const int MOD = 998244353; // 7*17*2^23 + 1
  const int MAXPWR = 22; // 随着MOD改变, 2的幂次, 对应复平面单位向量的N = 2 && MAXPWR;
  const int g = 3;// 原根 随着MOD改变
  const int invg = 332748118;// 原根模逆元 随着MOD 和 g 改变

  // bit 翻转
  int rev(int x, int len) {
    int ans = 0;
    while(len -- ){
      ans <<= 1;
      ans |= x & 1;
      x >>= 1;
    }
    return ans;
  }

  inline int getlog2(int n){ return 31 - __builtin_clz(n);}

  ll mypow(ll a, ll k) { //快速幂，a**k
    ll res = 1;
    while (k) {
      if (k & 1) (res *= a) %= MOD;
      (a *= a) %= MOD;
      k >>= 1;
    }
    return res;
  }

  void NTT(vector<ll> &A, int flag = 1 /* 1: NTT, -1: INTT*/ ) {
    int n = A.size();
    if(n == 1) return ;
    // assert((n & (n-1)) == 0); // 2 的幂次
    int lgn = getlog2(n);
    // assert(lgn <= MAXPWR);
    rep(i, 0, n) { // 同FFT
      int j = rev(i, lgn);
      if (j > i) swap(A[i], A[j]);
    }
    rep(pwr,0,lgn){
      int m = 1 << pwr;
      // assert((MOD - 1) % (m<<1) == 0);
      ll gn = mypow(flag == 1 ? g : invg, (MOD - 1) / (m << 1)); // 单位原根g_n
      for (int k = 0; k < n; k += (m<<1)) {
        ll gi = 1;
        rep(j,0,m) {
          auto U = A[k + j];
          auto T = gi * A[k + j + m] % MOD;
          A[k + j] = (U + T) % MOD;
          A[k + j + m] = (U - T + MOD) % MOD;
          (gi *= gn) %= MOD;
        }
      }
    }
    if(flag == -1){ // 内置 / N
      const ll INVSIZE = mypow(n, MOD-2);
      rep(i,0,n) (A[i] *= INVSIZE) %= MOD;
    }
  }

  void INTT(vector<ll> &A){ NTT(A,-1);}

  // 平方 少一次 NTT
  vector<ll> poly_sq(vector<ll> &v0) {
    int sz = v0.size() * 2;
    if(sz == 0)return {};
    sz = 1 << (getlog2(sz) + !!(sz & (sz-1))); // 非2的幂次
    v0.resize(sz,0);
    NTT(v0);
    vector<ll> a2(sz,0);
    rep(i,0,sz) a2[i] = v0[i] * v0[i] % MOD;
    INTT(a2);
    return a2;
  }
}

// ------------------------------- NTT --------------------------------

int n;

vector<ll> a;
vector<ll> b; // 滚动

int main(){
  const int MOD = NTT998::MOD;
  int n = read(); // 15
  int k = read(); // 2e5
  int f = read(); // 2e5
  if(f > 2 * k){
    printf("0\n");
    return 0;
  }
  b = vector<ll>(k+1,1);

  rep(i,1,n+1){
    // a
    a = NTT998::poly_sq(b); // 非平方也会TLE
    if(a.size() <= 2*k+1) a.resize(2*k+1,0);
    vector<ll> prea(2*k+2, 0); // prefix sum of a
    rep(j,0,2*k+1) prea[j+1] = (prea[j] + a[j]) % MOD;

    b = vector<ll>(k+1,0);
    rep(j,0,k+1) b[j] = (k-j+1) * a[j] % MOD + (prea[2*k+1] - prea[j+1]);
    while(!b.empty() && b.back() == 0) b.pop_back(); // 重要, 否则多出来的0 会导致 长度倍增 TLE
  }

  printf("%lld\n", a[f]);
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
const int POWER = 20;
const int N = 100000;
const int M = 200000;

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;
int m;
vector<int>p2[N+10]; // MST
pair<int,int> e[M+10]; // 边
bool treee[M+10]; // tree edge

int f[N+10]; // 并查集
int find(int v) {return f[v]==v?v:(f[v] = find(f[v]));}
void link(int u,int v){ f[find(v)] = find(u);}

ll x[N+10]; // 差分 和最终值
int fa[N+10][POWER]; // 树上倍增
int d[N+10]; // 深度
// 一级父节点 和 深度
void build(int u,int p = 1,int dep = 1){
  fa[u][0] = p;
  d[u] = dep;
  for(auto v:p2[u]) if(v != p) build(v,u,dep+1);
}
// 还原差分
void dfs(int u, int p = 1, int s = 0){
  x[u] += s;
  for(auto v:p2[u]) if(v != p) dfs(v,u,x[u]);
}
// 最近公共祖先
int lca(int u,int v){
  if(d[u] < d[v])swap(u,v); // d[u] > d[v]
  per(i,0,POWER) if(d[u] - d[v] >= (1 << i)) u = fa[u][i];
  if(u == v) return u;
  per(i,0,POWER) {
    if(fa[u][i] != fa[v][i]){
      u = fa[u][i];
      v = fa[v][i];
    }
  }
  return fa[u][0];
}
// u 向上走d步
int fa_d(int u,int d){
  per(i,0,POWER) if(d >= (1 << i)) {
    d -= (1<<i);
    u = fa[u][i];
  }
  return u;
}

int main(){
  // read
  n = read();
  m = read();
  rep(i,0,m){
    int u = read();
    int v = read();
    e[i] = {u,v};
  }
  // MST
  iota(f+1,f+n+1,1);
  rep(i,0,m){
    auto [u,v] = e[i];
    if(find(u) != find(v)) {
      treee[i] = true;
      link(u,v);
      p2[u].pb(v);
      p2[v].pb(u);
    }
  }
  // 建立倍增
  build(1); // 深度 和 1级父节点
  rep(pwr,1,POWER) rep(i,1,n+1) fa[i][pwr] = fa[fa[i][pwr-1]][pwr-1];

  // 树上差分
  rep(i,0,m) if(!treee[i]){
    auto [u,v] = e[i];
    if(d[u] > d[v]) swap(u,v); // d[u] < d[v];
    int r = lca(u,v);
    if(u == r){
      int w = fa_d(v, d[v] - d[u] - 1);
      x[w]++;
      x[v]--;
    } else {
      x[1]++;
      x[u]--;
      x[v]--;
    }
  }
  // 差分还原成值
  dfs(1);
  // 输出答案
  rep(i,1,n+1) printf("%d", (int)(x[i] == 0));
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

int MOD = -1;

ll read(){ll r;scanf("%lld",&r);return r;} // read
ll mpow(ll v,ll mi){ll r = 1;while(mi){if(mi%2)(r*=v)%=MOD;(v*=v)%=MOD;mi>>=1;};return r;} // quick power with MOD

int n;

vector<int> e[2010];

void dfs(int u,int fa){
  vector<int> arr = {};
  for(auto v: e[u]) if(v != fa) arr.pb(v);
  e[u] = arr;
  for(auto v: e[u]) dfs(v, u);
}

struct ModInt{
  int v;
  ModInt(ll val = 0) :v(val) { }
};

ll real(const ModInt & v0){
  return (v0.v + MOD) % MOD;
}

ModInt operator+(const ModInt & v0, const ModInt &v1){
  return (v0.v + v1.v) % MOD;
}

ModInt operator-(const ModInt & v0, const ModInt &v1){
  return (v0.v - v1.v) % MOD;
}

ModInt operator*(const ModInt & v0, const ModInt &v1){
  return ((ll)v0.v * (ll)v1.v) % MOD;
}

ModInt dp[2010][2010];
vector<ModInt> preMu[2010]; // 每次只会具体 u 可以复用
vector<ModInt> sufMu[2010];
ModInt S[2010][2010];
ModInt W[2010][2010];

ModInt fac[2010] = {1};
ModInt invv[2010] = {1};
ModInt invfac[2010] = {1};
ModInt C(int n,int m) { return fac[n] * invfac[m] * invfac[n-m]; }

ModInt ans[2010];

int main(){
  n = read();
  MOD = read();
  rep(i,1,n){
    int u = read();
    int v = read();
    e[u].pb(v);
    e[v].pb(u);
  }

  // 30 ms
  rep(i,1,n+1) fac[i] = fac[i-1] * i;
  invv[1] = 1;
  rep(i,2,n+1) invv[i] = (MOD-MOD/i) * invv[MOD % i];
  rep(i,1,n+1) invfac[i] = invfac[i-1] * invv[i];

  dfs(1, 1);
  // 61ms
  // bfs on tree
  vector<int> vorder = {1};
  rep(i, 0, vorder.size()) {
    int u = vorder[i];
    for(auto v: e[u]) vorder.pb(v);
  }
  reverse(vorder.begin(), vorder.end());

  for(auto u: vorder) {
    rep(t,1,n) {
      ModInt &dput = dp[u][t] = 1; // 叶子
      if(!e[u].empty()) {
        // 优化成 前后缀
        preMu[t] = vector<ModInt> (e[u].size() + 1, 1);
        sufMu[t] = vector<ModInt> (e[u].size() + 1, 1);
        rep(i,0,e[u].size()){
          auto v = e[u][i];
          preMu[t][i+1] = preMu[t][i] * S[v][t];
        }
        per(i,0,e[u].size()){
          auto v = e[u][i];
          sufMu[t][i] = sufMu[t][i+1] * S[v][t];
        }
        dput = preMu[t][e[u].size()];
        if(t > 1) rep(i,0,e[u].size()) {
          auto v = e[u][i];
          ModInt &Wvt = W[v][t-1] = ((t-1 > 1) ? W[v][t-2] : 0) + (preMu[t-1][i] * sufMu[t-1][i+1]);
          dput = dput + dp[v][t] * Wvt;
        }
      }
      S[u][t] = ((t > 1) ? S[u][t-1] : 0) + dput;
    }
  }

  rep(t,1,n) ans[t] = preMu[t][e[1].size()];
  rep(t,1,n) rep(t0,1,t) ans[t] = ans[t] - ans[t0] * C(t,t0) ;
  rep(t,1,n) printf("%lld ", real(ans[t]));
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
const int N = 100000;
const int PLEN = 19; // power length math.log(100000) / math.log(2) 16.609640474436812
const int POP = 35; // power operation math.log(4999950000) / math.log(2) 32.219266521851075
 
ll n;
 
int L[POP][PLEN][N+10]; // 次数不用记录零次
int R[POP][PLEN][N+10];
 
int LG2[N+10]; // 0 和 1 都对应0次方, 需要减的 1<<LG2[r-l]的偏移量
 
int a[N+10];
 
inline pii f(int l,int r,int p1){
  if(l == r) return {
    L[p1][0][l],
    R[p1][0][r]
  };
  int sz = LG2[r-l];
 
  return {
    min(L[p1][sz+1][l],L[p1][sz+1][r-(1<<sz)]),
    max(R[p1][sz+1][l],R[p1][sz+1][r-(1<<sz)])
  };
}
 
inline int query(int l,int r){
  if(l == 1 && r == n) return 0;
  if(l == r) return -1;
  // 不要二分, 二分是 log(n^2) = 2 log(n) * log(n)
  // 直接binary 倍增做, log(r-l+1)*O(1) < log(n)
  ll ret = 0;
  per(i, 0, POP){
    // printf("%d = %d\n",r-l,p0);
    int l0, r0;
    tie(l0, r0) = f(l, r, i);
    if(l0 != 1 || r0 != n){
      // checklrk(l, r, 1ll << i, l0, r0);
      l = l0;
      r = r0;
      ret += (1ll << i);
      if(l == r) return -1;
    }
  }
  tie(l,r) = f(l, r, 0);
  return (l == 1 && r == n) ? (ret + 1) : -1;
}
 
int main(){
  n = read();
  rep(i,2,N) LG2[i] = LG2[i/2] + 1;
  int q = read();
  rep(i,1,n+1) L[0][0][i] = R[0][0][i] = a[i] = read();
  {
    const int p1 = 0;
    rep(p0,1,PLEN) rep(i,1,n+1) {
      L[p1][p0][i] = min(L[p1][p0-1][i],L[p1][p0-1][min(n,i+(1ll << max(0ll, p0-2)))]);
      R[p1][p0][i] = max(R[p1][p0-1][i],R[p1][p0-1][min(n,i+(1ll << max(0ll, p0-2)))]);
      // check(i,p0,p1);
    }
  }
  rep(p1, 1, POP) rep(p0, 0, PLEN) rep(i,1,n+1){
    tie(
        L[p1][p0][i] ,
        R[p1][p0][i]
       ) = f(
         L[p1 - 1][p0][i],
         R[p1 - 1][p0][i],
         p1 - 1
         );
  }
 
  while(q--){
    int l = read();
    int r = read();
    printf("%d\n", query(l,r));
  }
  return 0;
}
 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

ll mul(ll a,ll b){
  a %= MOD;
  b %= MOD;
  return a * b % MOD;
}

ll add(ll a,ll b){
  a %= MOD;
  b %= MOD;
  return (a + b) % MOD;
}

ll normal(ll a){
  return (a%MOD + MOD)%MOD;
}

ll mypow(ll v,ll pwr){
  v%=MOD;
  ll r = 1;
  while(pwr){
    if(pwr%2) (r*=v)%=MOD;
    (v*=v)%=MOD;
    pwr/=2;
  }
  return r;
}

ll fac[300010] = {1};

ll binom(ll n,ll m){
  if(m > n) return 0;
  return fac[n] * mypow(fac[m],MOD-2) % MOD * mypow(fac[n-m],MOD-2) % MOD;
}

int main(){
  rep(i,1,300005) fac[i] = mul(fac[i-1],i);
  int n = read();
  ll k = read();
  ll ans = 0;
  ll binomk1s1 = 1; // k 很大
  rep(s,0,n+1){
    if(s > k) break;
    binomk1s1 = mul(binomk1s1,mul(k+1-s,mypow(s+1,MOD-2)));
    ans = add(ans,mul(mul(mypow(2,s),binom(n,s)),binomk1s1) );
  }

  printf("%lld\n", normal(ans));
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read
ll gcd(ll a,ll b){return b == 0?a:gcd(b,a%b);}

const int N = 300000;

int n,m;

vector<int> u2v[N+10]; // 正向边
vector<int> v2u[N+10]; // 反向边

ll w[N+10];
int invalid[N+10]; // 1 无效, 0 有效, -1 未访问
int fa[N+10]; // 并查集

// 并查集
int getfa(int v){ return v == fa[v]?v:(fa[v] = getfa(fa[v]));}
void link(int u,int v){ fa[getfa(u)] = getfa(v);}
// 计算不可达
bool dfs1n(int u){
  int &r = invalid[u];
  if(r != -1) return r;
  if(u == n) return r = 0;
  r = 1;
  for(auto v:u2v[u]) if(!dfs1n(v)) r = 0;
  return r;
}

// 移除不合法
vector<int> rminvalid(const vector<int> &arr){
  vector<int> ret = {};
  for(auto u: arr) if(!invalid[u]) ret.pb(u);
  return ret;
}

vector<pair<int,ll> > p2[N+10];
int vis[N+10];
ll dis[N+10]; // 和根的距离, root distance

void dfs(int idx,ll d,ll & ans) {
  if(vis[idx]) {
    // (环长 = 多树边 + 1回边), (重边), 多回边的环 gcd = 拆分的多个单回边环的gcd的gcd
    ans = gcd(ans, abs(d - dis[idx]) );
    return ;
  }
  vis[idx] = true;
  dis[idx] = d;
  for(auto [v,s]:p2[idx]) dfs(v, d + s, ans);
}

int main(){
  n = read();
  m = read();
  iota(fa,fa+n+1,0); // fa[i] = i
  fill(invalid+1,invalid+n+1,-1); // invalid[i] = -1
  rep(i,1,m+1) { // u -> v
    int u = read();
    int v = read();
    u2v[u].push_back(v);
    v2u[v].push_back(u);
  }
  rep(i,1,n+1) w[i] = read();
  // 筛无效点
  dfs1n(1);
  rep(u,1,n+1) if(!invalid[u]) u2v[u] = rminvalid(u2v[u]);
  rep(v,1,n+1) if(!invalid[v]) v2u[v] = rminvalid(v2u[v]);
  // n -> 1
  u2v[n].pb(1);
  v2u[1].pb(n);

  // 找所有点的源点, 计算并查集
  rep(v,1,n+1) if(!invalid[v]) rep(i,1,v2u[v].size()) link(v2u[v][i-1], v2u[v][i]);
  // 根据给定w 建立新的图
  rep(v,1,n+1) if(!invalid[v] && w[v] != -1){
    int tov = getfa(v); // 并查集中的点
    int fromv = getfa(v2u[v][0]); // assert(v2u[tov].size()); 因为都可达所以每个点一定有前置点
    // 全部双向边 辅助在有向图中找所有环的gcd
    p2[fromv].pb({tov, w[v]}); // 正向
    p2[tov].pb({fromv, -w[v]}); // 负向
  }
  // 找环
  ll ans = 0;
  rep(i,1,n+1) if(!invalid[i] && !vis[i]) dfs(i,0,ans);
  printf("%lld\n",ans == 0? -1: abs(ans));
  return 0;
}