#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000002022;
int ckadd(int a, int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int ckmul(int a, int b) {
return a * 1LL * b % MOD;
}
int ckpower(int a, int n) {
int res = 1;
while (n) {
if (n & 1)
res = ckmul(res, a);
a = ckmul(a, a);
n >>= 1;
}
return res;
}
int ckdiv(int a, int b) {
return ckmul(a, ckpower(b, MOD - 2));
}
const int N = (int)2e5 + 6;
int n, m;
int a[N];
int par[N];
int deg[N];
int ANS[N];
bool vis[N];
int solve(int v) {
for (int i = 0; i < n; i++) vis[i] = false;
while (v != -1) {
if (v < n) vis[v] = true;
v = par[v];
}
int prod = 1;
for (int i = 0; i < n; i++) if (!vis[i]) {
prod = ckmul(prod, deg[i]);
}
return prod;
}
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 = 0; i < n + m; i++) par[i] = P[i];
for (int i = 1; i < n + m; i++) deg[par[i]]++;
for (int i = n; i < n + m; i++) ANS[i] = solve(i);
}
int count_ways(int L, int R) {
for (int i = L; i <= R; i++) a[i] = 1 - a[i];
int ans = 0;
for (int i = n; i < n + m; i++) if (a[i] == 1) {
ans = ckadd(ans, ANS[i]);
}
return ans;
}
/*
3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6
*/
