#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000002022;
// int n, m;
// vector<pair<ll, ll>> segTree(2e5 + 5, {0, 0});
// vector<bool> lazy(2e5 + 5, false);
// pair<ll, ll> merge(pair<ll, ll> a, pair<ll, ll> b) {
// pair<ll, ll> res = {0, 0};
// (res.first += (2 * a.first * b.first)) %= MOD;
// (res.first += (a.first * b.second + a.second * b.first)) %= MOD;
// (res.second += (a.first * b.second + a.second * b.first)) %= MOD;
// (res.second += (2 * a.second * b.second)) %= MOD;
// return res;
// }
// void push_down(int cur, int treeLeft, int treeRight) {
// if (!lazy[cur]) return;
// swap(segTree[cur].first, segTree[cur].second);
// lazy[cur] = false;
// if (treeLeft == treeRight) return;
// lazy[cur * 2 + 1] = !lazy[cur * 2 + 1];
// lazy[cur * 2 + 2] = !lazy[cur * 2 + 2];
// }
// void setup(int cur, int treeLeft, int treeRight, int pos, pair<ll, ll> val) {
// if (pos < treeLeft || pos > treeRight) return;
// if (treeLeft == treeRight) {
// segTree[cur] = val;
// return;
// }
// int mid = (treeLeft + treeRight) / 2;
// setup(cur * 2 + 1, treeLeft, mid, pos, val);
// setup(cur * 2 + 2, mid + 1, treeRight, pos, val);
// segTree[cur] = merge(segTree[cur * 2 + 1], segTree[cur * 2 + 2]);
// }
// void update(int cur, int treeLeft, int treeRight, int qLeft, int qRight) {
// push_down(cur, treeLeft, treeRight);
// if (qRight < treeLeft || qLeft > treeRight) return;
// if (treeLeft >= qLeft && treeRight <= qRight) {
// lazy[cur] = true;
// push_down(cur, treeLeft, treeRight);
// return;
// }
// int mid = (treeLeft + treeRight) / 2;
// update(cur * 2 + 1, treeLeft, mid, qLeft, qRight);
// update(cur * 2 + 2, mid + 1, treeRight, qLeft, qRight);
// segTree[cur] = merge(segTree[cur * 2 + 1], segTree[cur * 2 + 2]);
// }
// void init(int N, int M, std::vector<int> P, std::vector<int> A) {
// n = N;
// m = M;
// for (int i = 0; i < M; ++i) {
// if (A[i]) setup(0, 1, M, i + 1, {0, 1});
// else setup(0, 1, M, i + 1, {1, 0});
// }
// }
// int count_ways(int L, int R) {
// update(0, 1, m, L - n + 1, R - n + 1);
// return segTree[0].second;
// }
int n, m;
vector<int> a;
vector<vector<int>> children;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
children.resize(N);
for (int i = 0; i < N + M; ++i) children[P[i]].push_back(i);
for (int &i : A) a.push_back(i);
}
int count_ways(int L, int R) {
for (int i = L - n; i <= R - n; ++i) a[i] = 1 - a[i];
vector<pair<ll, ll>> dp(n + m);
for (int i = 0; i < m; ++i) {
if (a[m]) dp[i + n] = {0, 1};
else dp[i + n] = {1, 0};
}
for (int i = n - 1; i >= 0; --i) {
auto &x = dp[children[i][0]], &y = dp[children[i][1]];
(dp[i].first += (2 * x.first * y.first)) %= MOD;
(dp[i].first += (x.first * y.second + x.second * y.first)) %= MOD;
(dp[i].second += (x.first * y.second + x.second * y.first)) %= MOD;
(dp[i].second += (2 * x.second * y.second)) %= MOD;
}
return dp[0].second;
}
