#include "circuit.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000002022;
ll n,m;
vector<ll> p,a;
vector<vector<ll>> con;
vector<pair<ll,ll>> stat;
void dfs(ll);
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n=N;
m=M;
p.assign(P.begin(),P.end());
a.assign(A.begin(),A.end());
con.resize(n);
for(ll i = 1;i<n+m;i++) con[p[i]].push_back(i);
stat.resize(n+m);
dfs(0);
}
void upd(ll i){
if (i>=n){
stat[i] = {a[i-n]==0,a[i-n]==1};
return;
}
ll c = con[i].size();
vector<ll> v(c+1,0),v0(c+1,0);
v[0] = 1;
for(ll j : con[i]){
auto [x,y] = stat[j];
for(ll i = 0;i<c;i++){
v0[i] += v[i]*x%mod;
v0[i+1] += v[i]*y%mod;
}
v.swap(v0);
fill(v0.begin(),v0.end(),0);
}
ll x = 0, y = 0;
for(ll j = 0;j<=c;j++){
x += v[j]*(c-j)%mod;
y += v[j]*j%mod;
}
stat[i] = {x%mod,y%mod};
}
void dfs(ll i){// 0, 1
if(i<n) for(ll j : con[i]) dfs(j);
upd(i);
}
int count_ways(int L, int R) {
for(ll i = L;i<=R;i++) {
a[i-n]^=1;
ll x = i;
upd(x);
while (x){
x = p[x];
upd(x);
}
}
return stat[0].second;
}
