#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
ll c01(pair<ll, ll> &a, pair<ll, ll> &b) // Cantidad de formas de obtener 0 si p es 1
{
return (a.fr * b.fr) % MOD;
}
ll c02(pair<ll, ll> &a, pair<ll, ll> &b) // Cantidad de formas de obtener 0 si p es 2
{
return (((a.fr * b.se) % MOD + (a.se * b.fr) % MOD) % MOD + c01(a, b)) % MOD;
}
ll c12(pair<ll, ll> &a, pair<ll, ll> &b) // Cantidad de formas de obtener 1 si p es 2
{
return (a.se * b.se) % MOD;
}
ll c11(pair<ll, ll> &a, pair<ll, ll> &b) // Cantidad de formas de obtener 1 si p es 1
{
return (((a.fr * b.se) % MOD + (a.se * b.fr) % MOD) % MOD + c12(a, b)) % MOD;
}
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--)
{
ll X = grafo[i][0], Y = grafo[i][1];
pair<ll, ll> 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)
{
ll X = grafo[nod][0], Y = grafo[nod][1];
lazy[X] = (lazy[X] + 1) % 2;
swap(p[X].fr, p[X].se);
lazy[Y] = (lazy[Y] + 1) % 2;
swap(p[Y].fr, p[Y].se);
lazy[nod]=0;
}
void up(ll nod)
{
ll X = grafo[nod][0], Y = grafo[nod][1];
pair<ll, ll> 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, nod * 2);
update(l, r, nod * 2 + 1);
up(nod);
}
int count_ways(int L, int R)
{
update(L, R, 0);
return p[0].se;
}
