#include "circuit.h"
#include <vector>
#include <stdlib.h>
using namespace std;
typedef vector<int> vi;
const int N = 100000, M = 100000, N_ = (1 << 18), MD = 1000002022; /* N_ = pow2(ceil(log2(N + M))) */
int *ej[N + M], eo[N + M];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int st1[N_ * 2], st2[N_ * 2], sum[N_ * 2], h_, n, m, n_; char lz[N_];
void pul1(int i) {
st1[i] = (long long) st1[i << 1 | 0] * st1[i << 1 | 1] % MD;
}
void build1(int *aa, int n) {
for (int i = 0; i < n_; i++)
st1[n_ + i] = i < n ? aa[i] : 1;
for (int i = n_ - 1; i > 0; i--)
pul1(i);
}
void update1(int i, int x) {
i += n_;
st1[i] = x;
while (i > 1)
pul1(i >>= 1);
}
void put2(int i) {
st2[i] = (sum[i] - st2[i] + MD) % MD;
if (i < n_)
lz[i] ^= 1;
}
void pus2(int i) {
if (lz[i])
put2(i << 1 | 0), put2(i << 1 | 1), lz[i] = 0;
}
void pul2(int i) {
if (!lz[i])
st2[i] = (st2[i << 1 | 0] + st2[i << 1 | 1]) % MD;
}
void push2(int i) {
for (int h = h_; h > 0; h--)
pus2(i >> h);
}
void pull2(int i) {
while (i > 1)
pul2(i >>= 1);
}
void build2(vi aa, int *ww, int n) {
for (int i = 0; i < n_; i++)
if (i < n)
sum[n_ + i] = ww[i], st2[n_ + i] = aa[i] == 1 ? ww[i] : 0;
else
sum[n_ + i] = 0, st2[n_ + i] = 0;
for (int i = n_ - 1; i > 0; i--) {
sum[i] = (sum[i << 1 | 0] + sum[i << 1 | 1]) % MD;
pul2(i);
}
}
void update2(int l, int r) {
int l_ = l += n_, r_ = r += n_;
push2(l_), push2(r_);
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
put2(l++);
if ((r & 1) == 0)
put2(r--);
}
pull2(l_), pull2(r_);
}
int ww[M];
void dfs(int i) {
if (i >= n)
ww[i - n] = st1[1];
else {
update1(i, 1);
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
dfs(j);
}
update1(i, eo[i]);
}
}
void init(int n1, int m_, vi pp, vi aa) {
n = n1, m = m_;
for (int i = 0; i < n + m; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (int i = 1; i < n + m; i++)
append(pp[i], i);
h_ = 0;
while (1 << h_ < n + m)
h_++;
n_ = 1 << h_;
build1(eo, n);
dfs(0);
build2(aa, ww, m);
}
int count_ways(int l, int r) {
l -= n, r -= n;
update2(l, r);
return st2[1];
}
