#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000002022;
const int MAXN = 1e3 + 5;
int A[MAXN];
vector<int> adj[MAXN];
int N, M;
void init(int _N, int _M, std::vector<int> P, std::vector<int> _A) {
N = _N;
M = _M;
for (int i = N; i < N + M; ++i) {
A[i] = _A[i - N];
}
for (int i = 1; i < N + M; ++i) {
adj[P[i]].push_back(i);
}
}
pair<ll, ll> calc(int node) {
if (node >= N) {
return {A[node] ^ 1, A[node] ^ 0};
}
int m = adj[node].size();
vector<pair<ll, ll>> arr(m);
vector<vector<ll>> dp(m + 1, vector<ll>(m + 1));
dp[0][0] = 1;
for (int i = 0; i < m; ++i) {
arr[i] = calc(adj[node][i]);
}
for (int i = 1; i <= m; ++i) {
dp[i][0] = (dp[i - 1][0] * arr[i - 1].first) % MOD;
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= m; ++j) {
dp[i][j] = (
dp[i - 1][j] * arr[i - 1].first % MOD
+
dp[i - 1][j - 1] * arr[i - 1].second % MOD
) % MOD;
}
}
ll res = 0;
for (int i = 1; i <= m; ++i) {
res = (res + dp[m][i] * i) % MOD;
}
ll tot = m;
for (int i = 0; i < m; ++i) {
tot = (tot * (arr[i].first + arr[i].second)) % MOD;
}
return {tot - res, res};
}
int count_ways(int L, int R) {
for (int i = L; i <= R; ++i) {
A[i] ^= 1;
}
return calc(0).second;
}
