#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
#define sz(x) int(x.size())
const ll mod = 1'000'002'022;
ll ad(ll a, ll b)
{
return (a+b)%mod;
}
ll mul(ll a, ll b)
{
return (a*b)%mod;
}
const int mx = 200'000;
vll Z(1 + mx, 0);
vll Zprod(1 + mx, 1);
vll coeff(1 + mx, 0);
vi children[1 + mx];
int N, M;
vi A;
ll res = 0;
void dfs(int u)
{
for(int v : children[u])
{
Z[u]++;
dfs(v);
if(Z[v] != 0)
Zprod[u] = mul(Zprod[u], Zprod[v]);
}
if(Z[u] != 0)
Zprod[u] = mul(Zprod[u], Z[u]);
// cerr << u << " : " << Z[u] << " | " << Zprod[u] << '\n';
}
void dfs2(int u, ll curr)
{
coeff[u] = curr;
// cerr << u << " -> " << curr << '\n';
ll fwd[1 + sz(children[u]) + 1];
ll bwd[1 + sz(children[u]) + 1];
fwd[0] = 1;
for(int e = 1; e <= sz(children[u]); e++)
fwd[e] = mul(fwd[e-1], Zprod[ children[u][e - 1] ]);
bwd[sz(children[u]) + 1] = 1;
for(int e = sz(children[u]); e >= 1; e--)
bwd[e] = mul(bwd[e+1], Zprod[ children[u][e - 1] ]);
for(int e = 1; e <= sz(children[u]); e++)
{
// cerr << e << " : " << curr << ' ' << fwd[e-1] << ' ' << bwd[e+1] << '\n';
dfs2(children[u][e - 1], mul(curr, mul(fwd[e-1], bwd[e+1])));
}
}
struct segtree
{
int l;
int r;
ll v[2];
int lp = 0; //1 -> flip 0 and 1
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r)
{
if(A[l])
{
v[0] = coeff[l];
v[1] = 0;
}
else
{
v[0] = 0;
v[1] = coeff[l];
}
}
else
{
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
v[0] = ad(left->v[0], right->v[0]);
v[1] = ad(left->v[1], right->v[1]);
}
}
void flip(int L, int R)
{
if(R < l || r < L) return;
else if(L <= l && r <= R)
{
lp = !lp;
swap(v[0], v[1]);
}
else
{
left->flip(L, R);
right->flip(L, R);
v[0 ^ lp] = ad(left->v[0], right->v[0]);
v[1 ^ lp] = ad(left->v[1], right->v[1]);
}
}
};
segtree S;
void init(int N_, int M_, vi P_, vi A_)
{
N = N_;
M = M_;
for(int i = 1; i < N+M; i++)
children[P_[i]].push_back(i);
dfs(0);
dfs2(0, 1);
A = vi(N, -1);
for(int a : A_)
A.push_back(a);
S = segtree(N, N+M-1);
}
int count_ways(int L, int R)
{
S.flip(L, R);
return S.v[0];
}
