#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll r = 1000002022, p, n;
vector<ll> en, nu, lz, wl, wr;
void upd(int a, int b, int i)
{
if (wl[i] >= b || wr[i] <= a)
return;
if (wl[i] >= a && wr[i] <= b)
{
lz[i] ^= 1;
return;
}
upd(a, b, 2 * i);
upd(a, b, 2 * i + 1);
nu[i] = en[i] = 0;
if (lz[2 * i])
{
nu[i] += en[2 * i];
en[i] += nu[2 * i];
}
else
{
nu[i] += nu[2 * i];
en[i] += en[2 * i];
}
if (lz[2 * i + 1])
{
nu[i] += en[2 * i + 1];
en[i] += nu[2 * i + 1];
}
else
{
nu[i] += nu[2 * i + 1];
en[i] += en[2 * i + 1];
}
}
void init(int N, int M, vector<int> P, vector<int> A)
{
n = N;
ll m = M, i, a, b;
vector<vector<int> > ch(n + m);
vector<ll> t(n + m), d(n + m), pf, sf;
for (i = 1; i < n + m; i++)
ch[P[i]].push_back(i);
for (i = n; i < n + m; i++)
t[i] = 1;
for (i = n - 1; i >= 0; i--)
{
t[i] = ch[i].size();
for (auto h : ch[i])
t[i] = t[i] * t[h] % r;
}
queue<int> q;
d[0] = 1;
q.push(0);
while (!q.empty())
{
a = q.front();
q.pop();
b = ch[a].size();
pf.resize(b + 1);
sf.resize(b + 1);
pf[0] = sf[b] = 1;
for (i = 0; i < b; i++)
pf[i + 1] = pf[i] * t[ch[a][i]] % r;
for (i = b - 1; i >= 0; i--)
sf[i] = sf[i + 1] * t[ch[a][i]] % r;
for (i = 0; i < b; i++)
{
d[ch[a][i]] = (pf[i] * sf[i + 1] % r) * d[a] % r;
q.push(ch[a][i]);
}
}
p = m;
while (p != (p & -p))
p++;
en.resize(2 * p);
nu.resize(2 * p);
lz.resize(2 * p);
wl.resize(2 * p);
wr.resize(2 * p);
for (i = p; i < 2 * p; i++)
{
nu[i] = 0;
en[i] = 0;
if (i < p + m)
{
if (A[i - p])
en[i] = d[i - p + n];
else
nu[i] = d[i - p + n];
}
lz[i] = 0;
wl[i] = i;
wr[i] = i + 1;
}
for (i = p - 1; i > 0; i--)
{
wl[i] = wl[2 * i];
wr[i] = wr[2 * i + 1];
lz[i] = 0;
nu[i] = nu[2 * i] + nu[2 * i + 1];
en[i] = en[2 * i] + en[2 * i + 1];
}
}
int count_ways(int L, int R)
{
upd(L - n + p, R - n + p + 1, 1);
if (lz[1])
return nu[1] % r;
return en[1] % r;
}
