#include "circuit.h"
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const ll MOD = 1000002022;
const int MAXN = 200200;
vector<int> adj[MAXN];
vector<ll> tree;
vector<int> lazy;
ll d[MAXN], sum[MAXN];
int in[MAXN], out[MAXN], cnt;
int x, y;
void update1(int node, int s, int e, int l, int r, int val) {
if(l > r || e < l || r < s) return;
if(l <= s && e <= r) {
tree[node] = tree[node]*val%MOD;
return;
}
int mid = s+e>>1;
update1(node<<1, s, mid, l, r, val); update1(node<<1|1, mid+1, e, l, r, val);
}
ll solve1(int node, int s, int e, int idx) {
if(e < idx || idx < s) return 1;
ll ans = tree[node];
if(s != e) {
int mid = s+e>>1;
ans = ans*solve1(node<<1, s, mid, idx)%MOD;
ans = ans*solve1(node<<1|1, mid+1, e, idx)%MOD;
}
return ans;
}
void update_lazy(int node, int s, int e) {
if(lazy[node]) {
tree[node] = (sum[e]-sum[s-1]-tree[node]+2*MOD)%MOD;
if(s != e) {
lazy[node<<1] = 1-lazy[node<<1];
lazy[node<<1|1] = 1-lazy[node<<1|1];
}
lazy[node] = 0;
}
}
void update2(int node, int s, int e, int l, int r) {
update_lazy(node, s, e);
if(l > r || e < l || r < s) return;
if(l <= s && e <= r) {
tree[node] = (sum[e]-sum[s-1]-tree[node]+2*MOD)%MOD;
if(s != e) {
lazy[node<<1] = 1-lazy[node<<1];
lazy[node<<1|1] = 1-lazy[node<<1|1];
}
return;
}
int mid = s+e>>1;
update2(node<<1, s, mid, l, r); update2(node<<1|1, mid+1, e, l, r);
tree[node] = (tree[node<<1] + tree[node<<1|1])%MOD;
}
void dfs(int here) {
in[here] = ++cnt;
for(int there : adj[here]) dfs(there);
out[here] = cnt;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
for(int i = 1; i < N+M; i++) adj[P[i]].push_back(i);
x = N, y = M;
dfs(0);
int h = (int)ceil(log2(x+y));
tree.resize(1 << (h+1), 1);
for(int i = 0; i < N; i++) {
update1(1, 1, cnt, 1, in[i]-1, adj[i].size());
update1(1, 1, cnt, out[i]+1, cnt, adj[i].size());
}
for(int i = N; i < N+M; i++) {
d[i] = solve1(1, 1, cnt, in[i]);
sum[i] = (sum[i-1] + d[i])%MOD;
}
tree.clear();
tree.resize(1 << (h+1));
lazy.resize(1 << (h+1));
for(int i = N; i < N+M; i++)
if(A[i-N])
update2(1, 1, x+y-1, i, i);
}
int count_ways(int L, int R) {
update2(1, 1, x+y-1, L, R);
update_lazy(1, 1, x+y-1);
return tree[1];
}
