#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n, m, onoff[101010], par[202020];
vector<int> adj[202020];
const long long MOD = 1000002022;
long long cnt[202020], wgt[202020], sum[101010];
void get_cnt(int v) {
if (v < n) cnt[v] = adj[v].size();
else cnt[v] = 1;
for (int i = 0; i < adj[v].size(); i++) {
int next = adj[v][i];
get_cnt(next);
cnt[v] = (cnt[v] * cnt[next]) % MOD;
}
}
void get_wgt(int v, long long w) {
if (v >= n) {
wgt[v] = w;
return;
}
vector<long long> prefix, suffix;
for (int i = 0; i < adj[v].size(); i++) {
prefix.push_back(cnt[adj[v][i]]);
suffix.push_back(cnt[adj[v][i]]);
}
reverse(suffix.begin(), suffix.end());
for (int i = 1; i < adj[v].size(); i++) {
prefix[i] = (prefix[i] * prefix[i - 1]) % MOD;
suffix[i] = (suffix[i] * suffix[i - 1]) % MOD;
}
for (int i = 0; i < adj[v].size(); i++) {
int next = adj[v][i];
long long t;
if (adj[v].size() > 1) {
if (i == 0) t = suffix[adj[v].size() - 2];
else if (i == adj[v].size() - 1) t = prefix[adj[v].size() - 2];
else t = (prefix[i - 1] * suffix[adj[v].size() - i - 2]) % MOD;
}
else t = 1;
get_wgt(next, (w * t) % MOD);
}
}
struct seg {
long long tree[404040];
int lazy[404040];
vector<long long> arr;
void init(int v, int st, int ed) {
if (st == ed) {
tree[v] = arr[st];
lazy[v] = 0;
return;
}
int mid = (st + ed) / 2;
init(2 * v, st, mid);
init(2 * v + 1, mid + 1, ed);
tree[v] = (tree[2 * v] + tree[2 * v + 1]) % MOD;
}
void update(int v, int st, int ed, int gs, int ge) {
if (lazy[v] % 2 == 1) {
tree[v] = (sum[ed] - sum[st - 1] - tree[v] + 2 * MOD) % MOD;
if (st != ed) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
if (gs > ed || ge < st) return;
if (gs <= st && ed <= ge) {
tree[v] = (sum[ed] - sum[st - 1] - tree[v] + 2 * MOD) % MOD;
if (st != ed) {
lazy[2 * v] += 1;
lazy[2 * v + 1] += 1;
}
return;
}
int mid = (st + ed) / 2;
update(2 * v, st, mid, gs, ge);
update(2 * v + 1, mid + 1, ed, gs, ge);
tree[v] = (tree[2 * v] + tree[2 * v + 1]) % MOD;
}
long long get(int v, int st, int ed, int gs, int ge) {
if (lazy[v] % 2 == 1) {
tree[v] = (sum[ed] - sum[st - 1] - tree[v] + 2 * MOD) % MOD;
if (st != ed) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
if (gs > ed || ge < st) return 0;
if (gs <= st && ed <= ge) return tree[v];
int mid = (st + ed) / 2;
return (get(2 * v, st, mid, gs, ge) + get(2 * v + 1, mid + 1, ed, gs, ge)) % MOD;
}
} sumtree;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
for (int i = 0; i < n + m; i++) par[i] = P[i];
for (int i = 0; i < m; i++) onoff[i] = A[i];
for (int i = 1; i < n + m; i++) {
adj[par[i]].push_back(i);
}
get_cnt(0);
get_wgt(0, 1);
//for (int i = n; i < n + m; i++) cout << wgt[i] << "\n";
for (int i = n; i < n + m; i++) sum[i] = (sum[i - 1] + wgt[i]) % MOD;
for (int i = 0; i < n; i++) sumtree.arr.push_back(0);
for (int i = n; i < n + m; i++) sumtree.arr.push_back(onoff[i - n] * wgt[i]);
sumtree.init(1, n, n + m - 1);
}
int count_ways(int L, int R) {
sumtree.update(1, n, n + m - 1, L, R);
return (sumtree.get(1, n, n + m - 1, n, n + m - 1)) % MOD;
}
