#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
const int MOD = 1000002022;
const int MAXN = 2e5 + 1;
vector<ll> grafo[MAXN];
ll lazy[MAXN];
pair<ll, ll> p[MAXN];
pair<ll, ll> rang[MAXN];
// En los comentarios p es el parametro del nodo
// Cantidad de formas de obtener 0 si p es 1
#define c01(a,b) ((a.fr * b.fr) % MOD)
// Cantidad de formas de obtener 0 si p es 2
#define c02(a,b) ((((a.fr * b.se) % MOD + (a.se * b.fr) % MOD) % MOD + c01(a, b)) % MOD)
// Cantidad de formas de obtener 1 si p es 2
#define c12(a,b) ((a.se * b.se) % MOD)
// Cantidad de formas de obtener 1 si p es 1
#define c11(a,b) ((((a.fr * b.se) % MOD + (a.se * b.fr) % MOD) % MOD + c12(a, b)) % MOD)
ll X, Y;
pair<ll, ll> x, y;
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
ll i, j;
for (i = 1; i < sz(P); i++)
grafo[P[i]].pb(i);
for (i = 0; i < sz(A); i++)
{
p[i + N] = {!A[i], A[i]};
rang[i + N] = {i + N, i + N};
}
for (i = N - 1; i >= 0; i--)
{
X = grafo[i][0], Y = grafo[i][1];
x = p[X], y = p[Y];
p[i] = {(c01(x, y) + c02(x, y)) % MOD, (c11(x, y) + c12(x, y)) % MOD};
rang[i] = {min(rang[X].fr, rang[Y].fr), max(rang[X].se, rang[Y].se)};
}
}
void prop(ll nod)
{
X = grafo[nod][0], Y = grafo[nod][1];
lazy[X] = (lazy[X] + lazy[nod]) % 2;
if(lazy[nod])
swap(p[X].fr, p[X].se);
lazy[Y] = (lazy[Y] + lazy[nod]) % 2;
if(lazy[nod])
swap(p[Y].fr, p[Y].se);
lazy[nod]=0;
}
void up(ll nod)
{
X = grafo[nod][0], Y = grafo[nod][1];
x = p[X], y = p[Y];
p[nod] = {(c01(x, y) + c02(x, y)) % MOD, (c11(x, y) + c12(x, y)) % MOD};
}
void update(ll l, ll r, ll nod)
{
if (rang[nod].fr > r || rang[nod].se < l)
return;
if (rang[nod].fr >= l && rang[nod].se <= r)
{
lazy[nod] = (lazy[nod] + 1) % 2;
swap(p[nod].fr, p[nod].se);
return;
}
prop(nod);
update(l, r, grafo[nod][0]);
update(l, r, grafo[nod][1]);
up(nod);
}
int count_ways(int L, int R)
{
update(L, R, 0);
return p[0].se;
}
