#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<int> p;
vector<int> a;
vector<vector<int>> adj;
int n, m;
const ll MOD = 1000002022;
const int mxN = 200000+5;
ll f[mxN][2];
void ordfs(int u) {
if (adj[u].size()==0) return;
int l = adj[u][0];
int r = adj[u][1];
ordfs(l);
ordfs(r);
f[u][0] = f[l][0]*f[r][1] + f[l][1]*f[r][0] + 2*f[l][0]*f[r][0];//formas de hacer u 0
f[u][0] %= MOD;
f[u][1] = f[l][0]*f[r][1] + f[l][1]*f[r][0] + 2*f[l][1]*f[r][1];
f[u][1] %= MOD;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
p = P;
n = N, m = M;
adj.assign(n+m, {});
for (int i=1; i<n+m; i++) {
adj[P[i]].push_back(i);
}
a = A;
memset(f, 0, sizeof(f));
for (int i=n; i<n+m; i++) {
f[i][a[i-n]] = 1;
}
ordfs(0);
}
void dfs(int u) {
if (u==-1) return;
if (adj[u].size()==0) {
dfs(p[u]);
return;
}
int l = adj[u][0];
int r = adj[u][1];
f[u][0] = f[l][0]*f[r][1] + f[l][1]*f[r][0] + 2*f[l][0]*f[r][0];//formas de hacer u 0
f[u][0] %= MOD;
f[u][1] = f[l][0]*f[r][1] + f[l][1]*f[r][0] + 2*f[l][1]*f[r][1];
f[u][1] %= MOD;
dfs(p[u]);
}
int count_ways(int L, int R) {
for (int i=L; i<=R; i++) {
f[i][a[i-n]] = 0;
a[i-n] ^= 1;
f[i][a[i-n]] = 1;
}
dfs(L);
return f[0][1];
}
