#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const ll mxN=2e5+5;
const ll mod=1000002022;
ll n, m;
vll adj[mxN];
vll a;
ll dp[mxN];
vll pre[mxN];
vll suf[mxN];
vll c;
struct segtree{
vll val, tree, lazy;
ll treelen;
void init(ll siz){
treelen=siz+1;
while(__builtin_popcount(treelen)!=1){
treelen++;
}
val=vll(2*treelen);
tree=vll(2*treelen);
lazy=vll(2*treelen);
}
void build(ll idx, ll low, ll high){
if(low==high){
if(low<m){
val[idx]=c[low];
tree[idx]=a[low]*c[low];
}
return;
}
ll mid=(low+high)/2;
build(2*idx, low, mid);
build(2*idx+1, mid+1, high);
val[idx]=val[2*idx]+val[2*idx+1];
val[idx]%=mod;
tree[idx]=tree[2*idx]+tree[2*idx+1];
tree[idx]%=mod;
}
void push(ll idx, ll low, ll high){
if(lazy[idx]){
tree[2*idx]=val[2*idx]-tree[2*idx];
tree[2*idx]%=mod;
if(tree[2*idx]<0) tree[2*idx]+=mod;
lazy[2*idx]^=1;
tree[2*idx+1]=val[2*idx+1]-tree[2*idx+1];
tree[2*idx+1]%=mod;
if(tree[2*idx+1]<0) tree[2*idx+1]+=mod;
lazy[2*idx+1]^=1;
lazy[idx]=0;
}
}
void update1(ll idx, ll low, ll high, ll qlow, ll qhigh){
if(low>=qlow && high<=qhigh){
tree[idx]=val[idx]-tree[idx];
tree[idx]%=mod;
if(tree[idx]<0) tree[idx]+=mod;
lazy[idx]^=1;
return;
}
if(low>qhigh || high<qlow){
return;
}
ll mid=(low+high)/2;
push(idx, low, high);
update1(2*idx, low, mid, qlow, qhigh);
update1(2*idx+1, mid+1, high, qlow, qhigh);
tree[idx]=tree[2*idx]+tree[2*idx+1];
tree[idx]%=mod;
}
void update(ll qlow, ll qhigh){
update1(1, 0, treelen-1, qlow, qhigh);
}
ll total(){
return tree[1];
}
};
segtree seg;
void dfs(ll cur){
if(cur>=n){
dp[cur]=1;
return;
}
dp[cur]=(ll) adj[cur].size();
for(auto &chd:adj[cur]){
dfs(chd);
dp[cur]*=dp[chd];
dp[cur]%=mod;
}
ll p=1;
pre[cur]=vll((ll) adj[cur].size());
for(ll i=0;i<(ll) adj[cur].size();i++){
p*=dp[adj[cur][i]];
p%=mod;
pre[cur][i]=p;
}
suf[cur]=vll((ll) adj[cur].size());
p=1;
for(ll i=(ll) adj[cur].size()-1;i>=0;i--){
p*=dp[adj[cur][i]];
p%=mod;
suf[cur][i]=p;
}
}
void dfs2(ll cur, ll val){
if(cur>=n){
c[cur-n]=val;
return;
}
for(ll i=0;i<(ll) adj[cur].size();i++){
ll new_val=val;
if(i>0){
new_val*=pre[cur][i-1];
new_val%=mod;
}
if(i<(ll) adj[cur].size()-1){
new_val*=suf[cur][i+1];
new_val%=mod;
}
dfs2(adj[cur][i], new_val);
}
}
}
void init(int N, int M, vector<int> P, vector<int> A) {
n=N;
m=M;
c=vll(m);
a=vll(m);
for(ll i=1;i<n+m;i++){
adj[P[i]].pb(i);
}
for(ll i=0;i<m;i++){
a[i]=A[i];
}
dfs(0);
dfs2(0, 1);
seg.init(m+1);
seg.build(1, 0, seg.treelen-1);
}
int count_ways(int L, int R) {
L-=n;
R-=n;
seg.update(L, R);
return (int) seg.total();
}
