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