#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<int> p;
vector<int> a;
vector<vector<int>> adj;
int n, m;
const ll MOD = 1000002022;
const int mxN = 200000+5;
ll f[mxN][2];
vector<int> h;
void ordfs(int u) {
if (adj[u].size()==0) return;
int l = adj[u][0];
int r = adj[u][1];
h[l] = h[u]+1;
h[r] = h[u]+1;
ordfs(l);
ordfs(r);
f[u][0] = f[l][0]*f[r][1] + f[l][1]*f[r][0] + 2*f[l][0]*f[r][0];//formas de hacer u 0
f[u][0] %= MOD;
f[u][1] = f[l][0]*f[r][1] + f[l][1]*f[r][0] + 2*f[l][1]*f[r][1];
f[u][1] %= MOD;
}
vector<int> lazy;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
lazy.assign(mxN, 0);
h.assign(mxN, 0);
h[0] = 0;
p = P;
n = N, m = M;
adj.assign(n+m, {});
for (int i=1; i<n+m; i++) {
adj[P[i]].push_back(i);
}
a = A;
memset(f, 0, sizeof(f));
for (int i=n; i<n+m; i++) {
f[i][a[i-n]] = 1;
}
ordfs(0);
}
int count_ways(int L, int R) {
for (int i=L; i<=R; i++) {
a[i-n] ^= 1;
}
ll ans=0;
for (int i=n; i<n+m; i++) {
ans += a[i-n]*(1<<(n-h[i]));
}
ans %= MOD;
return ans;
}
