#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;
vector<bool> lazy;
ll dp[MAXN][2];
void update(int node, int l, int r, int ql, int qr) {
if (ql > r or qr < l) return;
if (ql <= l and r <= qr) {
lazy[node] = !lazy[node];
swap(dp[node][0], dp[node][1]);
return;
}
int m = (l+r) / 2;
int left = down[node].front(), right = down[node].back();
if (lazy[node]) {
lazy[node] = false;
lazy[left] = !lazy[left];
swap(dp[left][0], dp[left][1]);
lazy[right] = !lazy[right];
swap(dp[right][0], dp[right][1]);
}
update(left, l, m, ql, qr);
update(right, m+1, r, ql, qr);
auto [l0, l1] = dp[left];
auto [r0, r1] = dp[right];
dp[node][0] = ((l0*r1) % MOD + (l1*r0) % MOD + (2LL*l0*r0) % MOD) % MOD;
dp[node][1] = ((l0*r1) % MOD + (l1*r0) % MOD + (2LL*l1*r1) % MOD) % MOD;
}
void init(int N, int M, vector<int> P, vector<int> A) {
memset(&dp[0][0], 0, sizeof(dp));
down.assign(N+M, {});
lazy.assign(N+M, false);
n = N, m = M, up = P, a = A;
for (int i = 1; i < N + M; 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 + (2LL*l0*r0) % MOD) % MOD;
dp[u][1] = ((l0*r1) % MOD + (l1*r0) % MOD + (2LL*l1*r1) % MOD) % MOD;
};
dfs(dfs, 0);
}
int count_ways(int L, int R) {
// we need to propagate...
update(0, 0, n-1, L-n, R-n);
return dp[0][1];
}
