#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000002022;
struct node {
ll sum, sum2;
};
node operator+(const node& a, const node& b) {
node ret;
ret.sum = (a.sum + b.sum) % MOD;
ret.sum2 = (a.sum2 + b.sum2) % MOD;
return ret;
}
struct segmentTree {
vector<node> tree;
vector<int> lazy;
void init(int n) {
int sz = (1 << (int)ceil(log2(n)) + 1);
tree.resize(sz);
lazy.resize(sz);
}
node updateVal(int x, node v, int l, int r, int n) {
if (r < x || x < l)
return tree[n];
if (l == r)
return tree[n] = v;
int m = (l + r) >> 1;
return tree[n] = updateVal(x, v, l, m, n << 1) + updateVal(x, v, m + 1, r, n << 1 | 1);
}
void propagate(int l, int r, int n) {
if (!lazy[n])
return;
swap(tree[n].sum, tree[n].sum2);
if (l != r) {
lazy[n << 1] = !lazy[n << 1];
lazy[n << 1 | 1] = !lazy[n << 1 | 1];
}
lazy[n] = 0;
}
node update(int lx, int rx, int l, int r, int n) {
propagate(l, r, n);
if (r < lx || rx < l)
return tree[n];
if (lx <= l && r <= rx) {
lazy[n] = !lazy[n];
propagate(l, r, n);
return tree[n];
}
int m = (l + r) >> 1;
return tree[n] = update(lx, rx, l, m, n << 1) + update(lx, rx, m + 1, r, n << 1 | 1);
}
};
int n, m;
vector<int> child[200000];
ll degs[200000];
ll dp[200000];
segmentTree st;
ll dfs(int v) {
int sz = (int)child[v].size();
ll& ret = degs[v] = max(sz, 1);
for (int i : child[v])
ret = ret * dfs(i) % MOD;
return ret;
}
void dfs2(int v, ll tmp) {
dp[v] = tmp;
int sz = (int)child[v].size();
vector<ll> pre(sz + 1), suf(sz + 1);
pre[0] = 1;
for (int i = 1; i <= sz; i++)
pre[i] = pre[i - 1] * degs[child[v][i - 1]] % MOD;
suf[sz] = 1;
for (int i = sz - 1; i >= 0; i--)
suf[i] = suf[i + 1] * degs[child[v][i]] % MOD;
for (int i = 0; i < sz; i++)
dfs2(child[v][i], tmp * pre[i] % MOD * suf[i + 1] % MOD);
}
void init(int _n, int _m, vector<int> p, vector<int> a) {
n = _n;
m = _m;
for (int i = 0; i < n + m; i++)
child[p[i]].push_back(i);
dfs(0);
dfs2(0, 1);
st.init(m);
for (int i = 0; i < m; i++) {
node cur = { dp[i + n],0 };
if (!a[i])
swap(cur.sum, cur.sum2);
st.updateVal(i, cur, 0, m - 1, 1);
}
}
int count_ways(int l, int r) {
st.update(l - n, r - n, 0, m - 1, 1);
st.propagate(0, m - 1, 1);
return st.tree[1].sum;
}
