#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 = 3e5 + 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, p[N], a[N], val[N], pw[N];
ll ans[N], dp[1001][1001];
vector <int> g[N];
void dfs(int v) {
int c = g[v].size();
val[v] = c;
if (!c)
val[v] = 1;
for (auto to : g[v]) {
dfs(to);
val[v] = val[v] * val[to] % M;
}
if (v > n)
ans[v] = a[v];
else {
dp[0][0] = 1;
for (int i = 1;i <= c;i++) {
dp[i][0] = 1;
for (int j = 1;j <= c;j++) {
dp[i][j] = (dp[i - 1][j] * mod(val[g[v][i - 1]] - ans[g[v][i - 1]]) % M + dp[i - 1][j - 1] * ans[g[v][i - 1]] % M) % M;
}
}
ans[v] = 0;
for (int i = c;i >= 1;i--) {
ans[v] = (ans[v] + dp[c][i]) % M;
}
}
}
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++) {
pw[i] = pw[i - 1] * 2 % M;
p[i] = P[i - 1] + 1;
g[p[i]].pb(i);
}
for (int i = n + 1;i <= n + m;i++)
a[i] = A[i - 1 - n];
}
int count_ways(int L, int R) {
L++, R++;
for (int j = L;j <= R;j++) {
a[j] ^= 1;
}
dfs(1);
// for (int i = 1;i <= n + m;i++)
// cout << ans[i] << ' ';
// cout << '\n';
return ans[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;
// }
