#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
const int N = 2e5 + 5, mod = 1000002022;
vector<int> adj[N];
int64_t dp[N][2], color[N];
void dfs(int u) {
if(adj[u].size() == 0) {
if(color[u]) dp[u][0] = 0, dp[u][1] = 1;
else dp[u][0] = 1, dp[u][1] = 0;
return;
}
for(int v: adj[u]) dfs(v);
vector<vector<int64_t>> D((int)adj[u].size() + 1, vector<int64_t>((int)adj[u].size() + 1));
D[0][0] = 1;
for(int i = 0; i < (int)adj[u].size(); ++i) {
for(int j = 0; j <= i; ++j) {
D[i + 1][j] += D[i][j] * dp[adj[u][i]][0] % mod;
D[i + 1][j] %= mod;
D[i + 1][j + 1] += D[i][j] * dp[adj[u][i]][1] % mod;
D[i + 1][j + 1] %= mod;
}
}
dp[u][0] = dp[u][1] = 0;
for(int i = 0; i <= (int)adj[u].size(); ++i) {
dp[u][1] += D[(int)adj[u].size()][i] * i % mod;
dp[u][1] %= mod;
dp[u][0] += D[(int)adj[u].size()][i] * ((int)adj[u].size() - i) % mod;
dp[u][0] %= mod;
}
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
for(int i = 1; i < N + M; ++i) {
adj[P[i]].push_back(i);
}
for(int i = 0; i < M; ++i) color[i + N] = A[i];
dfs(0);
}
int count_ways(int L, int R) {
for(int i = L; i <= R; ++i) {
color[i] ^= 1;
}
dfs(0);
return dp[0][1];
}
