#include "circuit.h"
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define f0r(i,n) for(int i = 0; i< n; i++)
#define mp make_pair
using namespace std;
vector<signed> par;
vector<signed> v;
vector<vi> adj;
int n,m;
const int mod = 1e9 + 2022;
const int mxn = 2e5 + 5;
vector<vi>dp(mxn, vi(2));
void recum(int node, int tl, int tr, int l, int r){
if(tr < l || tl > r)return;
if(tl == l && tr == r){
swap(dp[node - 1][0], dp[node - 1][1]);
}
else{
int tm = (tl + tr) / 2;
recum(node *2, tl, tm, l, min(tm, r));
recum(node * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
int i = node - 1;
int a = adj[i][0];
int b = adj[i][1];
dp[i][1] = dp[a][1] * dp[b][1] % mod * 2 % mod + dp[a][1] * dp[b][0] % mod + dp[b][1] * dp[a][0] % mod;
dp[i][1] %= mod;
dp[i][0] = dp[a][1] * dp[b][0] % mod + dp[b][1] * dp[a][0] % mod + dp[a][0] * dp[b][0] % mod * 2 % mod;
dp[i][0] %= mod;
}
}
void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
n = N; m = M; par = P; v = A;
adj.resize(n + m);
FOR(i, 1, n+m){
adj[P[i]].pb(i);
}
FOR(i, n, n + m){
if(v[i-n] == 1){
dp[i][1] = 1;
}
else dp[i][0] = 1;
}
for(int i = n - 1; i>=0; i--){
int a = adj[i][0];
int b = adj[i][1];
dp[i][1] = dp[a][1] * dp[b][1] % mod * 2 % mod + dp[a][1] * dp[b][0] % mod + dp[b][1] * dp[a][0] % mod;
dp[i][1] %= mod;
dp[i][0] = dp[a][1] * dp[b][0] % mod + dp[b][1] * dp[a][0] % mod + dp[a][0] * dp[b][0] % mod * 2 % mod;
dp[i][0] %= mod;
}
}
signed count_ways(signed l, signed r) {
recum(1, 0, m-1, l - n, r - n);
return dp[0][1];
}
