#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
vector<int> adj[200005];
int p[200005], vis[200005], arr[200005], brr[200005], seg1[4*200005], seg0[4*200005], s[4*200005], dep[200005], mod = 1000002022;
void lazypropagate(int n, int l, int r) {
if (s[n]) {
swap(seg1[n], seg0[n]);
if (l != r) {
s[2*n] ^= 1;
s[2*n+1] ^= 1;
}
s[n] = 0;
}
}
void build(int n, int l, int r) {
if (l == r) {
seg1[n] = arr[l];
seg0[n] = brr[l];
} else {
int m = (l+r)/2;
build(2*n, l, m);
build(2*n+1, m+1, r);
seg1[n] = seg1[2*n] + seg1[2*n+1];
seg1[n] %= mod;
seg0[n] = seg0[2*n] + seg0[2*n+1];
seg0[n] %= mod;
}
}
void update(int n, int l, int r, int a, int b) {
lazypropagate(n, l, r);
if (b < l || r < a) {
return;
} else if (a <= l && r <= b) {
s[n] = 1;
lazypropagate(n, l, r);
} else {
int m = (l+r)/2;
update(2*n, l, m, a, b);
update(2*n+1, m+1, r, a, b);
seg1[n] = seg1[2*n] + seg1[2*n+1];
seg1[n] %= mod;
seg0[n] = seg0[2*n] + seg0[2*n+1];
seg0[n] %= mod;
}
}
int n, m;
void dfs(int i) {
vis[i] = 1;
if (i != 0) {
dfs(p[i]);
}
}
void init(int32_t N, int32_t M, vector<int32_t> P, vector<int32_t> A) {
n = N, m = M;
for (int i = 1; i <= n+m-1; i++) {
p[i] = P[i];
adj[P[i]].push_back(i);
}
vector<int> b(n+1, 1);
for (int i = 1; i <= n; i++) {
b[i] = b[i-1]*2;
b[i] %= mod;
}
dfs(0);
for (int i = 0; i < m; i++) {
int v = 1;
for (int j = 0; j < n; j++) {
vis[j] = 0;
}
dfs(n+i);
for (int j = 0; j < n; j++) {
if (vis[j]) {
continue;
}
v *= adj[j].size();
v %= mod;
}
if (A[i]) {
arr[i] = v;
} else {
brr[i] = v;
}
}
build(1, 0, m-1);
}
int32_t count_ways(int32_t L, int32_t R) {
update(1, 0, m-1, L-n, R-n);
return seg1[1];
}
