#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000002022;
int add(int a, int b) {
a += b;
if (a >= MOD) return a - MOD;
if (a < 0) return a + MOD;
return a;
}
int mul(int a, int b) {
return a * (ll) b % MOD;
}
void addup(int &a, int b) {
a = add(a, b);
}
void mulup(int &a, int b) {
a = mul(a, b);
}
vector<int> c, now;
int dim, subtract;
void init(int n, int m, std::vector<int> par, std::vector<int> init) {
dim = m;
subtract = n;
c.resize(m, 0);
///cout << n << " " << m << " : " << (int) par.size() << " vs " << (int) init.size() << "\n";
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);
mulup(prod[a], prod[b]);
}
};
now = init;
function<void(int, int)> dfs = [&] (int a, int coef) {
/// optimize this function
for (int i = 0; i < (int) g[a].size(); i++) {
int send = coef;
for (int j = 0; j < (int) g[a].size(); j++) {
if (i != j) {
mulup(send, prod[g[a][j]]);
}
}
dfs(g[a][i], send);
}
if (g[a].empty()) {
assert(n + 0 <= a && a < n + m);
c[a - n] = coef;
}
};
build1(0);
dfs(0, 1);
}
int count_ways(int l, int r) {
l -= subtract;
r -= subtract;
assert((int) c.size() == dim);
assert((int) now.size() == dim);
assert(0 <= l && l <= r && r < dim);
for (int j = l; j <= r; j++) {
now[j] ^= 1;
}
int sol = 0;
for (int j = 0; j < dim; j++) {
addup(sol, mul(c[j], now[j]));
}
return sol;
}
