#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, fa;
vector <vector<int>> adj;
vector <ar<int,2>> 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, fa = P;
adj.resize(n + m);
for ( int i = 1; i < n + m; i++ ){
adj[P[i]].pb(i);
}
vector <int> s(n + m);
dp.resize(n + m);
auto dfs = [&](auto dfs, int u) -> void{
if ( u >= n ){
dp[u][1] = a[u - n];
dp[u][0] = a[u - n] ^ 1;
return;
}
for ( auto &v: adj[u] ){
dfs(dfs, v);
s[u] += 1;
}
vector <int> f(s[u] + 1);
f[0] = 1;
for ( auto &v: adj[u] ){
vector <int> nxt(s[u] + 1);
for ( int j = 0; j <= s[u]; j++ ){
add(nxt[j], f[j] * 1LL * dp[v][0] % Mod);
if ( j > 0 ){
add(nxt[j], f[j - 1] * 1LL * dp[v][1] % Mod);
}
}
swap(f, nxt);
}
for ( int i = 0; i <= s[u]; i++ ){
add(dp[u][1], i * 1LL * f[i] % Mod);
add(dp[u][0], (s[u] - i) * 1LL * f[i] % Mod);
}
};
dfs(dfs, 0);
}
int count_ways(int L, int R) {
L -= n, R -= n;
for ( int i = L; i <= R; i++ ){
a[i] ^= 1;
}
for ( int i = L; i <= R; i++ ){
int u = i + n;
while ( u != -1 ){
if ( u >= n ){
dp[u][1] = a[u - n];
dp[u][0] = a[u - n] ^ 1;
} else{
int s = (int)adj[u].size();
vector <int> f(s + 1);
f[0] = 1;
for ( auto &v: adj[u] ){
vector <int> nxt(s + 1);
for ( int j = 0; j <= s; j++ ){
add(nxt[j], f[j] * 1LL * dp[v][0] % Mod);
if ( j > 0 ){
add(nxt[j], f[j - 1] * 1LL * dp[v][1] % Mod);
}
}
swap(f, nxt);
}
dp[u] = {0, 0};
for ( int i = 0; i <= s; i++ ){
add(dp[u][1], i * 1LL * f[i] % Mod);
add(dp[u][0], (s - i) * 1LL * f[i] % Mod);
}
}
u = fa[u];
}
}
return dp[0][1];
}
