#include<bits/stdc++.h>
#include "circuit.h"
using namespace std;
#define fint signed
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
const int MX = 2e5+5;
const int mod = 1e9+2022;
int NS, MS;
struct segment_tree
{
vector<int> tree; vector<int> sum; vector<bool> lazy;
void build(const vector<fint> &val, const vector<fint> &st, int id, int l, int r)
{
int m = (l+r)/2;
if(l == r)
{
sum[id] = val[m];
tree[id] = (st[m] ? val[m] : 0ll);
return;
}
build(val, st, 2*id, l, m);
build(val, st, 2*id+1, m+1, r);
tree[id] = (tree[2*id]+tree[2*id+1])%mod;
sum[id] = (sum[2*id]+sum[2*id+1])%mod;
return;
}
void push(int id)
{
if(!lazy[id])
return;
lazy[2*id] = lazy[2*id+1] = 1;
tree[2*id] = (sum[2*id]-tree[2*id]+mod)%mod;
tree[2*id+1] = (sum[2*id+1]-tree[2*id+1]+mod)%mod;
lazy[id] = 0;
return;
}
void init(const vector<fint> &val, const vector<fint> &st, int n)
{
tree.resize(4*n+5);
sum.resize(4*n+5);
lazy.assign(4*n+5, false);
build(val, st, 1, 0, n-1);
return;
}
void upd(int ql, int qr, int id, int l, int r)
{
//cout << "Called " << endl;
if(qr < l || r < ql)
return;
if((ql <= l) && (r <= qr))
{
tree[id] = (sum[id]-tree[id]+mod)%mod;
lazy[id] = lazy[id]^1;
return;
}
push(id);
int m = (l+r)/2;
upd(ql, qr, 2*id, l, m);
upd(ql, qr, 2*id+1, m+1, r);
tree[id] = (tree[2*id]+tree[2*id+1])%mod;
return;
}
int Q()
{
return tree[1];
}
};
segment_tree work;
int oth[MX];
int prod[MX];
vector<fint> val;
vector<int> adj[MX];
void dfs(int u)
{
prod[u] = max(1ll, (int)adj[u].size());
vector<int> w;
for(int v: adj[u])
{
dfs(v);
w.pb(prod[v]);
prod[u]*=prod[v]; prod[u]%=mod;
}
//cout << "Running u = " << u << endl;
int n = w.size();
if(w.empty())
return;
int pref[n];
int suff[n];
pref[0] = w[0];
for(int i = 1; i < n; i++)
pref[i] = (pref[i-1]*w[i])%mod;
suff[n-1] = w[n-1];
for(int i = n-2; i >= 0; i--)
suff[i] = (suff[i+1]*w[i])%mod;
int cnt = 0;
for(int v: adj[u])
{
oth[v] = 1;
if(cnt > 0)
oth[v]*=pref[cnt-1];
if(cnt < (n-1))
oth[v]*=suff[cnt+1];
oth[v]%=mod;
cnt++;
}
return;
}
void dfs2(int u, int VL = 1)
{
if(u >= NS)
{
//cout << "Called u = " << u << " and VL = " << VL << endl;
val[u-NS] = VL;
}
for(int v: adj[u])
{
int VL_p = (VL*oth[v])%mod;
dfs2(v, VL_p);
}
return;
}
void init(fint n, fint m, vector<fint> p, vector<fint> a)
{
NS = n;
MS = m;
for(int i = 0; i < n+m; i++)
adj[i].clear();
for(int i = 1; i < n+m; i++)
adj[p[i]].pb(i);
val.resize(m);
dfs(0); dfs2(0);
/*cout << "r - ";
for(int i = n; i < n+m; i++)
cout << val[i-n] << " ";
cout << "\n";*/
//cout << "Hey " << endl;
work.init(val, a, m);
return;
}
fint count_ways(fint L, fint R)
{
int l = L-NS;
int r = R-NS;
work.upd(l, r, 1, 0, MS-1);
return (fint)work.Q();
}
