#include "circuit.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
#define ll long long
struct node
{
ll on=0,of=0,swp=0;
};
int const NPM=2e5+10,mod=1000002022;
vector<int>nei[NPM]={};
long long dp[NPM]={};
vector<long long>pre[NPM]={};
vector<long long>suf[NPM]={};
int ans[NPM]={};
bool op[NPM]={};
node seg[4*NPM]={};
int n,m;
long long mul(ll a,ll b)
{
return (a*b)%mod;
}
long long add(ll a,ll b)
{
return (a+b)%mod;
}
void build(int i,int st,int en)
{
if (st==en)
{
if (op[st])
seg[i].on=ans[st];
else
seg[i].of=ans[st];
return;
}
int mid=(st+en)/2;
build(i*2,st,mid);
build(i*2+1,mid+1,en);
seg[i].on=add(seg[i*2].on,seg[i*2+1].on);
seg[i].of=add(seg[i*2].of,seg[i*2+1].of);
}
void push(int i)
{
for (int j=2*i;j<=2*i+1;j++)
{
seg[j].swp^=1;
swap(seg[j].on,seg[j].of);
}
seg[i].swp=0;
}
void update(int i,int st,int en,int l,int r)
{
if (st>=l&&en<=r)
{
swap(seg[i].on,seg[i].of);
seg[i].swp=1;
return;
}
if (st>r||en<l)
return;
if (seg[i].swp)
push(i);
int mid=(st+en)/2;
update(i*2,st,mid,l,r);update(i*2+1,mid+1,en,l,r);
seg[i].on=add(seg[i*2].on,seg[i*2+1].on);
seg[i].of=add(seg[i*2].of,seg[i*2+1].of);
}
void comp(int u,ll val=1)
{
if (u>=n)
ans[u-n]=val;
int sz=nei[u].size();
for (int i=0;i<sz;i++)
comp(nei[u][i],mul(mul(val,pre[u][i]),suf[u][i+1]));
}
void dfs(int u)
{
dp[u]=1;
pre[u]={1};
suf[u]={1};
if (nei[u].size()==0)
return;
for (auto i:nei[u])
{
dfs(i);
dp[u]=mul(dp[i],dp[u]);
pre[u].push_back(mul(pre[u].back(),dp[i]));
}
dp[u]=mul(dp[u],nei[u].size());
int sz=nei[u].size();
for (int i=sz-1;i>=0;i--)
suf[u].push_back(mul(suf[u].back(),dp[nei[u][i]]));
reverse(begin(suf[u]),end(suf[u]));
}
void init(int N, int M, vector<int> P, vector<int> A)
{
n=N;
m=M;
for (int i=1;i<n+m;i++)
nei[P[i]].push_back(i);
dfs(0);
comp(0);
for (int i=0;i<m;i++)
op[i]=A[i];
build(1,0,m-1);
}
int count_ways(int L, int R)
{
update(1,0,m-1,L-n,R-n);
return seg[1].on;
}
