#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define pb push_back
#define ln '\n'
const int Mod = 1000002022;
vector <int> a;
vector <vector<int>> adj;
vector <int> dp;
int n, m;
template <class F, class S>
void add(F &x, const S &y){
x = (x + 0LL + y) % Mod;
if ( x < 0 ) x += Mod;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
a = A, n = N, m = M;
adj.resize(n + m);
for ( int i = 1; i < n + m; i++ ){
adj[P[i]].pb(i);
}
vector <int> s(n + m);
dp.resize(m);
auto dfs = [&](auto dfs, int u, int cnt) -> void{
if ( u >= n ){
dp[u - n] = cnt;
return;
}
int s = adj[u].size();
vector <int> child, vl;
for ( auto &v: adj[u] ){
int x = adj[v].size();
child.pb(v); vl.pb(max(1, x));
}
vector <int> pf(s + 1, 1), sf(s + 2, 1);
for ( int i = 0; i < s; i++ ){
pf[i + 1] = pf[i] * 1LL * vl[i] % Mod;
}
for ( int i = s; i > 0; i-- ){
sf[i] = sf[i + 1] * 1LL * vl[i - 1] % Mod;
}
for ( int i = 0; i < s; i++ ){
int nxt = cnt * 1LL * pf[i] % Mod * sf[i + 2] % Mod;
dfs(dfs, child[i], nxt);
}
};
dfs(dfs, 0, 1);
}
int count_ways(int L, int R) {
L -= n, R -= n;
int cnt = 0;
for ( int i = L; i <= R; i++ ){
a[i] ^= 1;
}
for ( int i = 0; i < m; i++ ){
add(cnt, a[i] * dp[i]);
}
return cnt;
}
