#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int MAXN = 3e5+10;
const ll MOD = 1e9+2022;
ll sum(ll a, ll b){ return (a+b)%MOD;}
void chsum(ll &a, ll b){ a = (a+b)%MOD;}
ll mul(ll a, ll b){ return (a*b)%MOD; }
void chmul(ll &a, ll b){ a = (a*b)%MOD;}
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
int n, m, par[MAXN], a[MAXN];
ll dp[MAXN][3];
vector<int> adj[MAXN];
void dfs(int nw, int pa){
for(auto nx : adj[nw]){
dfs(nx, nw);
}
if(adj[nw].size() == 0){
dp[nw][0] = dp[nw][1] = 0;
if(a[nw] == 1) dp[nw][1] = 1;
else dp[nw][0] = 1;
return;
}
int le = adj[nw][0], ri = adj[nw][1];
dp[nw][1] = sum(sum( mul(dp[le][1],dp[ri][0]), mul(dp[le][0], dp[ri][1])),
mul(2, mul(dp[le][1], dp[ri][1] ) ) ); // nyala
dp[nw][0] = sum(sum( mul(dp[le][1],dp[ri][0]), mul(dp[le][0], dp[ri][1])),
mul(2, mul(dp[le][0], dp[ri][0] ) ) ); // mati
}
void bd(int nw){
if(nw == 0) return;
if(adj[nw].size() == 0){
dp[nw][0] = dp[nw][1] = 0;
if(a[nw] == 1) dp[nw][1] = 1;
else dp[nw][0] = 1;
bd(par[nw]);
return;
}
int le = adj[nw][0], ri = adj[nw][1];
dp[nw][1] = sum(sum( mul(dp[le][1],dp[ri][0]), mul(dp[le][0], dp[ri][1])),
mul(2, mul(dp[le][1], dp[ri][1] ) ) ); // nyala
dp[nw][0] = sum(sum( mul(dp[le][1],dp[ri][0]), mul(dp[le][0], dp[ri][1])),
mul(2, mul(dp[le][0], dp[ri][0] ) ) ); // mati
bd(par[nw]);
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N; m = M;
for(int i=1; i<=n+m; i++){
par[i] = P[i-1]+1;
adj[par[i]].pb(i);
}
for(int i=1; i<=m; i++){
a[i+n] = A[i-1];
}
dfs(1, 0);
}
int count_ways(int L, int R) {
int l = L+1, r = R+1;
for(int i=l; i<=r; i++) a[i] = 1-a[i];
bd(l);
// for(int i=1; i<=3; i++){
// cout << dp[i][0] << ' ' << dp[i][1] << " xx\n";
// }
return (int)dp[1][1];
}
