#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
int n,m;
const int mod=1000002022;
vector<int> a;
vector<vector<int>> g;
long long dp[100001][2];
void dfs(int v){
if(v>=n){
return;
}
dp[v][0]=dp[v][1]=0;
int sz=(int)g[v].size();
long long b[sz+1],c[sz+1];
for(int i=0;i<=sz;i++){
b[i]=c[i]=0;
}
b[0]=1;
for(auto x:g[v]){
dfs(x);
for(int i=0;i<sz;i++){
c[i+1]+=(dp[x][1]*b[i])%mod;
c[i]+=(dp[x][0]*b[i])%mod;
c[i+1]%=mod;
c[i]%=mod;
b[i]=c[i];
c[i]=0;
}
b[sz]=c[sz];
c[sz]=0;
}
long long sum=b[0];
for(int i=1;i<=sz;i++){
dp[v][0]+=sum;
dp[v][0]%=mod;
sum+=b[i];
sum%=mod;
}
sum=0;
for(int i=sz;i>=1;i--){
sum+=b[i];
sum%=mod;
dp[v][1]+=sum;
dp[v][1]%=mod;
}
}
void init(int N, int M, vector<int> P, vector<int> A) {
n=N;
m=M;
a=A;
g.resize(n+m);
for(int i=1;i<n+m;i++){
g[P[i]].push_back(i);
}
for(int i=0;i<m;i++){
dp[n+i][a[i]]=1;
dp[n+i][1-a[i]]=0;
}
}
int count_ways(int L, int R) {
for(int i=L;i<=R;i++){
a[i-n]=1-a[i-n];
dp[i][a[i-n]]=1;
dp[i][1-a[i-n]]=0;
}
dfs(0);
int res=dp[0][1];
return res;
}
