#include "circuit.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#define pb push_back
#define eb emplace_back
#define md ((tl + tr) >> 1)
#define TL v + v, tl, md
#define TR v + v + 1, md + 1, tr
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll M = 1000002022;
const ll INF = 1e18 + 7;
ll mod(ll a, ll b = M) {
if (a < 0)
a = b + a % b;
return a % b;
}
int n, m, pr[N], sz[N];
ll x[N], pw[N], a[N], p[N], t[4 * N], s[4 * N];
vector <int> g[N];
void build(int v = 1, int tl = n + 1, int tr = n + m) {
if (tl == tr) {
t[v] = x[tl] * a[tl];
s[v] = x[tl];
return;
}
build(TL), build(TR);
t[v] = (t[v + v] + t[v + v + 1]) % M;
s[v] = (s[v + v] + s[v + v + 1]) % M;
}
void push(int v) {
if (p[v]) {
t[v + v] = mod(s[v + v] - t[v + v]);
p[v + v] ^= 1;
t[v + v + 1] = mod(s[v + v + 1] - t[v + v + 1]);
p[v + v + 1] ^= 1;
p[v] = 0;
}
}
void upd(int l, int r, int v = 1, int tl = n + 1, int tr = n + m) {
if (tl >= l and tr <= r) {
t[v] = mod(s[v] - t[v]);
p[v] ^= 1;
return;
}
if (tl > r or l > tr)
return;
push(v);
upd(l, r, TL), upd(l, r, TR);
t[v] = (t[v + v] + t[v + v + 1]) % M;
}
void precalc(int v) {
sz[v] = 1;
if (v > n)
sz[v] = 0;
for (auto to : g[v]) {
precalc(to);
sz[v] += sz[to];
}
}
void dfs(int v) {
if (v <= n) {
x[g[v][0]] = x[v] * pw[sz[g[v][1]]] % M;
x[g[v][1]] = x[v] * pw[sz[g[v][0]]] % M;
dfs(g[v][0]), dfs(g[v][1]);
}
}
void init(int N, int M, vector <int> P, vector <int> A) {
n = N, m = M;
pw[0] = 1;
pw[1] = 2;
for (int i = 2;i <= n + m;i++) {
pr[i] = P[i - 1] + 1;
pw[i] = pw[i - 1] * 2 % M;
g[pr[i]].pb(i);
}
for (int i = n + 1;i <= n + m;i++) {
a[i] = A[i - n - 1];
}
precalc(1);
x[1] = 1;
dfs(1);
build();
}
int count_ways(int L, int R) {
L++, R++;
upd(L, R);
return t[1];
}
// void solve() {
// int n, m, q;
// cin >> n >> m >> q;
// vector <int> p(n + m), a(m);
// for (int i = 0;i < n + m;i++)
// cin >> p[i];
// for (int i = 0;i < m;i++)
// cin >> a[i];
// init(n, m, p, a);
// while (q--) {
// int l, r;
// cin >> l >> r;
// cout << count_ways(l, r) << '\n';
// }
// }
// signed main() {
// solve();
// return 0;
// }
