#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
const ll MOD = 1000002022;
const int MAXN = 2e5+5;
int n, m;
vector<vector<int>> down;
vector<int> up;
vector<int> a;
ll dp[MAXN][2];
void init(int N, int M, vector<int> P, vector<int> A) {
memset(&dp[0][0], 0, sizeof(dp));
down.assign(N+M, {});
n = N, m = M, up = P, a = A;
for (int i = 1; i < N + M; i++) {
// down[i].push_back(P[i]);
down[P[i]].push_back(i);
}
auto dfs = [&](auto &&dfs, int u) -> void {
if (down[u].empty()) {
dp[u][0] = a[u-n] == 0;
dp[u][1] = a[u-n] == 1;
return;
}
// two children
assert(down[u].size() == 2);
int l = down[u].front(), r = down[u].back();
dfs(dfs, l); dfs(dfs, r);
auto [l0, l1] = dp[l];
auto [r0, r1] = dp[r];
dp[u][0] = ((l0*r1) % MOD + (l1*r0) % MOD + (2*l0*r0) % MOD) % MOD;
dp[u][1] = ((l0*r1) % MOD + (l1*r0) % MOD + (2*l1*r1) % MOD) % MOD;
};
dfs(dfs, 0);
}
int count_ways(int L, int R) {
assert(L == R);
// we need to propagate...
swap(dp[L][0], dp[L][1]);
int u = up[L];
while (u != -1) {
int l = down[u].front(), r = down[u].back();
auto [l0, l1] = dp[l];
auto [r0, r1] = dp[r];
dp[u][0] = ((l0*r1) % MOD + (l1*r0) % MOD + (2*l0*r0) % MOD) % MOD;
dp[u][1] = ((l0*r1) % MOD + (l1*r0) % MOD + (2*l1*r1) % MOD) % MOD;
u = up[u];
}
return dp[0][1];
}
