#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];
ll n, m, tot=0;
pair<ll,ll>dfs(ll nod) // fr: posibilidades activo, se: posibilidades apagado
{
if(nod>=n)
return{val[nod],!val[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
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;
for(i=1; i<sz(P); i++)
grafo[P[i]].pb(i);
for(i=0; i<sz(A); i++)
val[i+N]=A[i];
n=N;
m=M;
}
int count_ways(int L, int R) {
ll i;
for(i=L; i<=R; i++)
val[i]=!val[i];
calc();
return tot;
}
