#include <bits/stdc++.h>
using namespace std;
template <class B>
struct LazySegTree : public B {
using T_q = typename B::T_q;
using T_u = typename B::T_u;
int n, sz, log; vector<T_q> seg; vector<T_u> lazy;
LazySegTree(int n = 0): n(n), log(__lg(max(n - 1, 1)) + 1) {
sz = (1 << log), seg.resize(sz << 1, B::e_q), lazy.resize(sz << 1, B::e_u);
}
LazySegTree(vector<T_q> & init): n((int) init.size()), log(__lg(max(n - 1, 1)) + 1) {
sz = (1 << log), seg.resize(sz << 1, B::e_q), lazy.resize(sz << 1, B::e_u);
copy(init.begin(), init.end(), seg.begin() + sz);
for(int i = sz - 1; i > 0; i--) refresh(i);
}
void refresh(int ind) {
seg[ind] = B::comb(seg[2 * ind], seg[2 * ind + 1]);
}
void app(int ind, int lo, int hi, T_u delta) {
seg[ind] = B::upd(seg[ind], delta, lo, hi);
lazy[ind] = B::comb_upd(delta, lazy[ind]);
}
void push(int ind, int lo, int hi) {
if(lo != hi) {
int mid = (lo + hi) >> 1;
app(2 * ind, lo, mid, lazy[ind]);
app(2 * ind + 1, mid + 1, hi, lazy[ind]);
}
lazy[ind] = B::e_u;
}
void push_from_root(int ind) {
ind += sz;
for(int i = log; i > 0; i--) {
push(ind >> i, (ind >> i << i) - sz, (((ind >> i) + 1) << i) - sz - 1);
}
}
T_q qry(int lo, int hi) {
push_from_root(lo), push_from_root(hi); T_q ret1 = B::e_q, ret2 = B::e_q;
for(lo += sz, hi += sz; lo <= hi; lo >>= 1, hi >>= 1) {
if(lo & 1) ret1 = B::comb(ret1, seg[lo++]);
if(hi & 1 ^ 1) ret2 = B::comb(seg[hi--], ret2);
}
return B::comb(ret1, ret2);
}
void upd(int lo, int hi, T_u delta) {
push_from_root(lo), push_from_root(hi); lo += sz, hi += sz;
for(int l = lo, r = hi, lvl = 0; l <= r; l >>= 1, r >>= 1, ++lvl) {
if(l & 1) app(l, (l << lvl) - sz, (l + 1 << lvl) - sz - 1, delta), l++;
if(r & 1 ^ 1) app(r, (r << lvl) - sz, (r + 1 << lvl) - sz - 1, delta), r--;
}
for(int i = 1; i <= log; i++) {
if(lo >> i << i != lo) refresh(lo >> i);
if((hi + 1) >> i << i != hi + 1) refresh(hi >> i);
}
}
};
const int mod = 1000002022;
struct Monoid {
using T_q = pair<int, int>; static constexpr T_q e_q = {0, 0};
using T_u = bool; static const T_u e_u = false;
T_q comb(T_q a, T_q b) {
return {(a.first + b.first) % mod, (a.second + b.second) % mod};
}
T_q upd(T_q a, T_u b, int l, int r) {
if(b) {
return {(a.second - a.first + mod) % mod, a.second};
}
return a;
}
T_u comb_upd(T_u a, T_u b) {
// a after b
return a ^ b;
}
};
int tot;
LazySegTree<Monoid> lst;
void init(int n, int m, vector<int> p, vector<int> a) {
tot = n;
vector<vector<int>> g(n);
vector<int> prod(n + m, 1);
vector<pair<int, int>> val(m);
for(int i = 1; i < n + m; i++) {
g[p[i]].push_back(i);
}
auto dfs = [&](auto rec, int u) -> void {
prod[u] = (int) g[u].size();
for(int v: g[u]) {
if(v < n) {
rec(rec, v);
prod[u] = (1LL * prod[u] * prod[v]) % mod;
}
}
};
auto dfs2 = [&](auto rec, int u, int down) {
if(u >= n) {
val[u - n].second = down;
return;
}
int sz = (int) g[u].size(), pf = 1;
vector<int> sf;
for(int v: g[u]) sf.push_back(prod[v]);
sf.push_back(1);
for(int i = sz - 1; i >= 0; i--) sf[i] = (1LL * sf[i] * sf[i + 1]) % mod;
for(int i = 0; i < sz; i++) {
int other = (1LL * pf * sf[i + 1]) % mod;
rec(rec, g[u][i], (1LL * other * down) % mod);
pf = (1LL * pf * prod[g[u][i]]) % mod;
}
};
dfs(dfs, 0);
dfs2(dfs2, 0, 1);
for(int i = 0; i < m; i++) {
val[i].first = a[i] * val[i].second;
}
lst = LazySegTree<Monoid>(val);
}
int count_ways(int l, int r) {
lst.upd(l - tot, r - tot, true);
return lst.seg[1].first;
}
