#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000002022;
struct Vertex {
int s0, s1;
};
vector<int> c, now;
int dim, subtract;
vector<Vertex> tree;
vector<int> lazy;
void build(int v, int tl, int tr) {
lazy[v] = 0;
if (tl == tr) {
tree[v].s0 = now[tl] * c[tl];
tree[v].s1 = (1 - now[tl]) * c[tl];
} else {
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
tree[v].s0 = tree[2 * v].s0 + tree[2 * v + 1].s0;
tree[v].s1 = tree[2 * v].s1 + tree[2 * v + 1].s1;
if (tree[v].s0 >= MOD) tree[v].s0 -= MOD;
if (tree[v].s1 >= MOD) tree[v].s1 -= MOD;
}
}
void push(int v, int tl, int tr) {
if (lazy[v]) {
swap(tree[v].s0, tree[v].s1);
if (tl < tr) lazy[2 * v] ^= 1, lazy[2 * v + 1] ^= 1;
lazy[v] = 0;
}
}
void op(int v, int tl, int tr, int l, int r) {
push(v, tl, tr);
if (tr < l || r < tl) return;
if (l <= tl && tr <= r) {
lazy[v] ^= 1;
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
op(2 * v, tl, tm, l, r);
op(2 * v + 1, tm + 1, tr, l, r);
tree[v].s0 = tree[2 * v].s0 + tree[2 * v + 1].s0;
tree[v].s1 = tree[2 * v].s1 + tree[2 * v + 1].s1;
if (tree[v].s0 >= MOD) tree[v].s0 -= MOD;
if (tree[v].s1 >= MOD) tree[v].s1 -= MOD;
}
void init(int n, int m, std::vector<int> par, std::vector<int> init) {
dim = m;
tree.resize(4 * dim + 7);
lazy.resize(4 * dim + 7);
subtract = n;
c.resize(m, 0);
vector<vector<int>> g(n + m);
vector<int> prod(n + m, 1);
for (int i = 1; i < n + m; i++) {
g[par[i]].push_back(i);
}
function<void(int)> build1 = [&] (int a) {
if (g[a].empty()) return;
prod[a] = (int) g[a].size();
for (auto &b : g[a]) {
build1(b);
prod[a] = prod[a] * (ll) prod[b] % MOD;
}
};
now = init;
function<void(int, int)> dfs = [&] (int a, int coef) {
/// optimize this function
vector<int> send((int) g[a].size());
{
int c = 1;
for (int i = 0; i < (int) g[a].size(); i++) {
send[i] = coef * (ll) c % MOD;
c = c * (ll) prod[g[a][i]] % MOD;
}
}
{
int c = 1;
for (int i = (int) g[a].size() - 1; i >= 0; i--) {
send[i] = send[i] * (ll) c % MOD;
c = c * (ll) prod[g[a][i]] % MOD;
}
}
for (int i = 0; i < (int) g[a].size(); i++) {
dfs(g[a][i], send[i]);
}
if (g[a].empty()) {
c[a - n] = coef;
}
};
build1(0);
dfs(0, 1);
build(1, 0, dim - 1);
}
int count_ways(int l, int r) {
op(1, 0, dim - 1, l - subtract, r - subtract);
push(1, 0, dim - 1);
return tree[1].s0;
}
