#include "circuit.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < ll(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= ll(l); --x)
typedef long long ll;
using namespace std;
const int mod = 1'000'002'022;
const int N = 200'010;
vector<int> A[N];
ll kol[N];
ll val[N];
void dfskol(int v)
{
if (A[v].empty()) {
kol[v] = 1;
return;
}
kol[v] = A[v].size();
for (int u : A[v]) {
dfskol(u);
kol[v] = kol[v] * kol[u] % mod;
}
}
void dfsval(int v, ll val)
{
if (A[v].empty()) {
::val[v] = val;
return;
}
vector<ll> vec;
for (int u : A[v])
vec.push_back(kol[u]);
vector<ll> pre = {1}, suf = {1};
Loop (i,0,vec.size()-1)
pre.push_back(pre.back() * vec[i] % mod);
LoopR (i,1,vec.size())
suf.push_back(suf.back() * vec[i] % mod);
reverse(suf.begin(), suf.end());
Loop (i,0,A[v].size())
dfsval(A[v][i], val * pre[i] % mod * suf[i] % mod);
}
namespace seg {
ll val[N];
bool state[N];
int st, fi;
void init(int l, int r, ll *v, int *s) {
st = l;
fi = r;
Loop (i,st,fi) {
val[i] = v[i];
state[i] = s[i];
}
}
void up(int l, int r) {
Loop (i,l,r)
state[i] = !state[i];
}
ll get() {
ll ans = 0;
Loop (i,st,fi) {
ans += state[i]? val[i]: 0;
ans %= mod;
}
return ans;
}
}
void init(int n, int m, std::vector<int> P, std::vector<int> A) {
Loop (i,1,n+m)
::A[P[i]].push_back(i);
dfskol(0);
dfsval(0, 1);
seg::init(n, n+m, val, A.data() - n);
}
int count_ways(int L, int R) {
seg::up(L, R+1);
return seg::get();
}
