#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int y = 1000002022;
int n, m;
vector<int> p, a;
vector<vector<int>> g;
vector<ll> cw, aw;
ll fcw(int x){
if (x >= n) return cw[x] = a[x-n];
//cout << x << " " << g[x].size() << "\n";
//cout << fcw(g[x][0]) << " " << fcw(g[x][1]) << " " << aw[g[x][0]] << " " << aw[g[x][1]] << "\n";
return cw[x] = (((fcw(g[x][0])*aw[g[x][1]]) % y) + ((fcw(g[x][1])*aw[g[x][0]] % y)) % y);
}
ll faw(int x){
//cout << x << "\n";
if (x >= n) return aw[x] = 1;
ll res = g[x].size();
for (int next : g[x]) res = (res*faw(next)) % y;
return aw[x] = res;
}
void init(int N, int M, vector<int> P, vector<int> A){
n = N;
m = M;
p = P;
a = A;
g.resize(N);
for (int i=1; i<N+M; i++) g[p[i]].push_back(i);
cw.resize(N+M);
aw.resize(N+M);
faw(0);
}
int count_ways(int L, int R){
for (int i=L; i<=R; i++) a[i-n] = 1-a[i-n];
int f = 0;
for (int i=0; i<m; i++){
if (a[i]) f++;
}
return f;
/*for (int i=0; i<m; i++) cout << a[i] << " ";
cout << "\n";*/
/*fcw(0);
for (int i=0; i<n+m; i++) cout << aw[i] << " ";
cout << "\n";
for (int i=0; i<n+m; i++) cout << cw[i] << " ";
cout << "\n";
return cw[0];*/
return fcw(0);
}
