#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];
void ordfs(int u) {
if (adj[u].size()==0) return;
int l = adj[u][0];
int r = adj[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);
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 L, R;
void prop(int u, int l, int r) {
if (lazy[u]&1) {
swap(f[u][1], f[u][0]);
}
if (l!=r) {
int s1 = 2*u+1;
int s2 = 2*u+2;
lazy[s1] = (lazy[s1]+lazy[u])%2;
lazy[s2] = (lazy[s2]+lazy[u])%2;
}
lazy[u] = 0;
}
void update(int u, int l, int r) {
prop(u, l, r);
if (l>R || r<L) return;
if (L<=l && r<=R) {
//cout << l << " " << r << " " << u << endl;
lazy[u] = (lazy[u]+1)%2;
prop(u, l, r);
return;
}
int m = (l+r)/2;
update(2*u+1, l, m);
update(2*u+2, m+1, r);
int s1 = 2*u+1;
int s2 = 2*u+2;
f[u][0] = f[s1][0]*f[s2][1] + f[s1][1]*f[s2][0] + 2*f[s1][0]*f[s2][0];//formas de hacer u 0
f[u][0] %= MOD;
f[u][1] = f[s1][0]*f[s2][1] + f[s1][1]*f[s2][0] + 2*f[s1][1]*f[s2][1];
f[u][1] %= MOD;
}
int count_ways(int l, int r) {
l -= n;
r -= n;
L=l, R=r;
update(0, 0, m-1);
return f[0][1];
}
