#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1000002022; //2*223*2242157
const ll mod=2242157;
const int c=2e5+5;
struct num{
ll _2,_223,_rest;
};
ll power(ll a, ll b, ll m){
ll res=1;
while(b){
if(b&1){
res*=a;
res%=m;
}
a*=a; a%=m; b>>=1;
}
return res;
}
num div(num a, num b){
num res;
res._2=a._2-b._2;
res._223=a._223-b._223;
res._rest=a._rest*power(b._rest,mod-2,mod)%mod;
return res;
}
num mul(num a, num b){
num res;
res._2=a._2+b._2;
res._223=a._223+b._223;
res._rest=a._rest*b._rest%mod;
return res;
}
num valt(ll a){
num res;
res._2=0;
while(a%2==0){
++res._2; a/=2;
}
res._223=0;
while(a%223==0){
++res._223; a/=223;
}
res._rest=a%mod;
return res;
}
ll vissza(num a){
return power(2,a._2,MOD)*power(223,a._223,MOD)%MOD*a._rest%MOD;
}
int n,m;
vector<int> adj[c];
num db[c];
num arr[c];
num all;
bool szin[c];
int _N,_M;
void dfs(int v, int p, num cur){
db[v]=cur;
cur=div(cur,arr[v]);
for(int x: adj[v]){
if(x != p){
dfs(x,v,cur);
}
}
}
pair<ll,ll> add(pair<ll,ll> a, pair<ll,ll> b){
return make_pair((a.first+b.first)%MOD,(a.second+b.second)%MOD);
}
pair<ll,ll> tree[4*c];
bool lazy[4*c];
void build(int v, int l, int r){
if(l==r){
if(!szin[l+_N]) tree[v]=make_pair(vissza(db[l+_N]),0);
else tree[v]=make_pair(0,vissza(db[l+_N]));
return;
}
int mid=l+r>>1;
build(2*v,l,mid); build(2*v+1,mid+1,r);
tree[v]=add(tree[2*v],tree[2*v+1]);
}
void update(int v, int l, int r, int x, int y){
if(lazy[v]){
swap(tree[v].first,tree[v].second);
if(l != r){
lazy[2*v]=lazy[2*v]^1;
lazy[2*v+1]=lazy[2*v+1]^1;
}
lazy[v]=0;
}
if(l>r || l>y || x>r || x>y) return;
if(x<=l && r<=y){
swap(tree[v].first,tree[v].second);
if(l != r){
lazy[2*v]=lazy[2*v]^1;
lazy[2*v+1]=lazy[2*v+1]^1;
}
return;
}
int mid=l+r>>1;
update(2*v,l,mid,x,y); update(2*v+1,mid+1,r,x,y);
tree[v]=add(tree[2*v],tree[2*v+1]);
}
void init(int N, int M, vector<int> P, vector<int> A){
int n=N+M;
_N=N; _M=M;
all._2=0; all._223=0; all._rest=1;
for(int i=1;i<=n;i++){
if(i>N) szin[i]=A[i-N-1];
if(i != 1){
adj[i].push_back(P[i-1]+1);
adj[P[i-1]+1].push_back(i);
}
}
for(int i=1;i<=n;i++){
if(i==1){
arr[i]=valt(adj[i].size());
all=mul(all,arr[i]);
}
else if(i<=N){
arr[i]=valt(adj[i].size()-1);
all=mul(all,arr[i]);
}
else arr[i]=valt(1);
}
dfs(1,0,all);
build(1,1,M);
}
int count_ways(int L, int R){
L=L-_N+1; R=R-_N+1;
update(1,1,_M,L,R);
return tree[1].second;
}
/*int main(){
init(3,4,{-1, 0, 1, 2, 1, 1, 0},{1, 0, 1, 0});
cout << count_ways(3,4) << '\n';
cout << count_ways(4,5) << '\n';
cout << count_ways(3,6) << endl;
}*/
