#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 MAXN = 2e5 + 1;
const int MOD = 1000002022;
vector<ll> grafo[MAXN];
ll val[MAXN], p[MAXN];
ll n, m, tot = 0;
pair<ll, ll> memo[MAXN];
pair<ll, ll> dfs(ll nod) // fr: posibilidades activo, se: posibilidades apagado
{
if (nod >= n)
{
memo[nod]={val[nod], !val[nod]};
return memo[nod];
}
pair<ll, ll> cant = {0, 0}, iz = dfs(grafo[nod][0]), der = dfs(grafo[nod][1]);
cant.fr = (2ll * (iz.fr * der.fr) % MOD) % MOD; // los dos en 1 (*2 pq se puede dejar en 1 con al menos 1 activo y con al menos 2 activos)
cant.fr = (cant.fr + (iz.fr * der.se) % MOD) % MOD; // solo el de la izquierda activo
cant.fr = (cant.fr + (der.fr * iz.se) % MOD) % MOD; // solo el de la derecha activo
cant.se = (2ll * (iz.se * der.se) % MOD) % MOD; // los 2 apagados
cant.se = (cant.se + (iz.fr * der.se) % MOD) % MOD; // solo 1 activo con al menos 2 activos
cant.se = (cant.se + (iz.se * der.fr) % MOD) % MOD; // solo 1 activo con al menos 2 activos
memo[nod] = cant;
return cant;
}
void calc()
{
pair<ll, ll> a = dfs(0);
tot = a.fr;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
ll i;
p[0] = -1;
for (i = 1; i < sz(P); i++)
{
p[i] = P[i];
grafo[P[i]].pb(i);
}
for (i = 0; i < sz(A); i++)
val[i + N] = A[i];
n = N;
m = M;
calc();
}
void update(ll x)
{
if (x == -1)
return;
pair<ll, ll> cant = {0, 0}, iz = memo[grafo[x][0]], der = memo[grafo[x][1]];
cant.fr = (2ll * (iz.fr * der.fr) % MOD) % MOD; // los dos en 1 (*2 pq se puede dejar en 1 con al menos 1 activo y con al menos 2 activos)
cant.fr = (cant.fr + (iz.fr * der.se) % MOD) % MOD; // solo el de la izquierda activo
cant.fr = (cant.fr + (der.fr * iz.se) % MOD) % MOD; // solo el de la derecha activo
cant.se = (2ll * (iz.se * der.se) % MOD) % MOD; // los 2 apagados
cant.se = (cant.se + (iz.fr * der.se) % MOD) % MOD; // solo 1 activo con al menos 2 activos
cant.se = (cant.se + (iz.se * der.fr) % MOD) % MOD; // solo 1 activo con al menos 2 activos
memo[x] = cant;
update(p[x]);
}
int count_ways(int L, int R)
{
ll i;
for(i=L; i<=R; i++)
{
val[i] = !val[i];
memo[i]={val[i], !val[i]};
update(p[i]);
}
return memo[0].fr;
}
