#include <bits/stdc++.h>
#define mp(x...) array<int, 2>({x})
#define pb push_back
using namespace std;
#include "circuit.h"
constexpr static int MXN = 2e5;
constexpr static int MOD = 1000002022;
constexpr static int MXST = MXN<<2;
int mul() { return 1; }
template<typename... V>
int mul(int64_t a, V... v) { return (a* mul(v...)) % MOD; }
int add() { return 0; }
template<typename... V>
int add(int a, V... v) { return (a+add(v...)) % MOD; }
//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
int n, m;
vector<int> p;
vector<int> a;
vector<int> g[MXN];
int factor[MXN];
int pcount[MXN];
void calculate(int i);
static inline int mul(int64_t a, int64_t b) { return (a*b) % MOD; }
static inline int add(int a, int b) { return (a+b) % MOD; }
struct SegTree
{
int n;
array<int, 2> data[MXST];
bitset<MXST> lazy;
array<int, 2> merge(array<int, 2> a, array<int, 2> b)
{
return mp(add(a[0], b[0]), add(a[1], b[1]));
}
void push(int l, int r, int index)
{
if (lazy[index] == 1)
swap(data[index][0], data[index][1]);
if (r - l > 1)
{
lazy[index<<1] = lazy[index<<1] ^ lazy[index];
lazy[(index<<1)|1] = lazy[(index<<1)|1] ^ lazy[index];
}
lazy[index] = 0;
}
void build(int l, int r, int index, vector<int>& a, vector<int>& f)
{
if (r - l == 1)
{
data[index][0] = mul((a[l]^1), f[l]);
data[index][1] = mul(a[l], f[l]);
debug(l, data[index]);
return;
}
int m = l+r>>1;
build(l, m, index<<1, a, f);
build(m, r, (index<<1)|1, a, f);
data[index] = merge(data[index<<1], data[(index<<1)|1]);
debug(l, r, data[index]);
}
void toggle(int l, int r, int index, int ss, int ee)
{
push(l, r, index);
if (ss >= r || l >= ee)
return;
if (ee >= r && l >= ss)
{
lazy[index] = lazy[index] ^ 1;
push(l, r, index);
debug(l, r, data[index]);
return;
}
int m = l+r>>1;
toggle(l, m, index<<1, ss, ee);
toggle(m, r, (index<<1)|1, ss, ee);
data[index] = merge(data[index<<1], data[(index<<1)|1]);
debug(l, r, data[index]);
}
int query(int l, int r, int index, int ss, int ee)
{
push(l, r, index);
if (ss >= r || l >= ee)
return 0;
if (ee >= r && l >= ss)
return data[index][1];
int m = l+r>>1;
int lres = query(l, m, index<<1, ss, ee);
int rres = query(m, r, (index<<1)|1, ss, ee);
return add(lres, rres);
}
};
SegTree st;
void dfs1(int node)
{
if (node >= n)
pcount[node] = 1;
else
pcount[node] = g[node].size();
for (int c : g[node])
{
dfs1(c);
pcount[node] = mul(pcount[node], pcount[c]);
}
}
void dfs2(int node)
{
vector<int> pf(g[node].size()+1), sf(g[node].size()+1);
pf[0] = 1, sf[g[node].size()] = 1;
for (int i = 1; i <= g[node].size(); i++)
pf[i] = mul(pf[i-1], pcount[g[node][i-1]]);
for (int i = g[node].size()-1; i >= 0; i--)
sf[i] = mul(sf[i+1], pcount[g[node][i]]);
for (int i = 0; i < g[node].size(); i++)
{
int c = g[node][i];
factor[c] = mul(factor[node],pf[i], sf[i+1]);
dfs2(c);
}
}
void init(int N, int M, vector<int> P, vector<int> A)
{
n = N;
m = M;
p = P;
a = A;
for (int i = 1; i < n+m; i++)
g[p[i]].pb(i);
dfs1(0);
factor[0] = 1;
dfs2(0);
vector<int> as;
for (int i = n; i < n+m; i++)
as.pb(factor[i]);
st.build(0, m, 1, a, as);
}
int count_ways(int l, int r)
{
debug(l-n, r-n+1);
st.toggle(0, m, 1, l-n, r-n+1);
return st.query(0, m, 1, 0, m);
}
