#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
constexpr int N = 2e5 + 5;
constexpr int mod = 1000002022;
vector<int> a, lvl;
vector<long long> dp;
vector<vector<int>> g;
int m;
void op(int i, int x, int y) {
int all = (1LL << lvl[i]) % mod;
dp[i] = 2 * dp[x] * dp[y] % mod + (all - dp[x]) * dp[y] % mod + (all - dp[y]) * dp[x] % mod;
dp[i] %= mod;
}
void init(int n, int _m, vector<int> p, vector<int> c) {
m = _m;
a.resize(n + m);
g.resize(n + m);
dp.resize(n + m);
lvl.resize(n + m);
for (int i = 1; i < n + m; i++) {
g[i].push_back(p[i]);
g[p[i]].push_back(i);
}
for (int i = 0; i < m; i++) {
a[i + n] = c[i];
dp[i + n] = c[i];
}
for (int i = n - 1; i >= 0; i--) {
lvl[i] = lvl[2 * i + 1] + 1;
}
for (int i = n - 1; i >= 0; i--) {
int x = i * 2 + 1, y = i * 2 + 2;
op(i, x, y);
}
}
int count_ways(int l, int r) {
assert(l == r);
int i = l;
dp[i] ^= 1;
while (i > 0) {
int p = (i - 1) / 2;
int x = 2 * p + 1, y = x + 1;
op(p, x, y);
i = p;
}
return dp[0];
}
