#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
const int cox[4] = {1, 0, -1, 0};
const int coy[4] = {0, -1, 0, 1};
const ll mod = 1000002022, pr = 31;
const int mxn = 2e5 + 5, mxd = 250 * 250, sq = 500, mxv = 2e6 + 1;
const int max_iter = 8e4, global_iter = 15e5 + 5;
//const int base = (1 <<18);
const ll inf = 1e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
//#include "circuit.h"
#include <vector>
int n, m;
vt<int>adj[mxn + 1];
ll sub[mxn + 1], val[mxn + 1], pref[mxn + 1], suf[mxn + 1], a[mxn + 1];
ll st[4 * mxn + 1], sm[4 * mxn + 1];
bool lz[4 * mxn + 1];
void dfs(int s){
sub[s] = 1;
for(auto i: adj[s]){
dfs(i); sub[s] = (sub[s] * sub[i]) % mod;
}
if(sz(adj[s])){
sub[s] = (sub[s] * sz(adj[s])) % mod;
}
}
void dfs2(int s, ll mul){
if(s >= n)val[s - n] = mul;
vt<ll>pref(sz(adj[s]) + 1), suf(sz(adj[s]) + 1);
pref[0] = 1;
for(int i = 0; i < sz(adj[s]); i++){
pref[i + 1] = (pref[i] * sub[adj[s][i]]) % mod;
}
suf[sz(adj[s])] = 1;
for(int i = sz(adj[s]) - 1; i >= 0; i--){
suf[i] = (suf[i + 1] * sub[adj[s][i]]) % mod;
}
for(int i = 0; i < sz(adj[s]); i++){
ll cool = (pref[i] * suf[i + 1]) % mod;
dfs2(adj[s][i], (mul * cool) % mod);
}
}
void pull(int nd){
st[nd] = (st[nd << 1] + st[nd << 1 | 1]) % mod;
sm[nd] = (sm[nd << 1] + sm[nd << 1 | 1]) % mod;
}
void build(int nd, int l, int r){
if(l == r){
st[nd] = a[l] * val[l]; sm[nd] = val[l];
return;
}
int mid = (l + r) >> 1;
build(nd << 1, l, mid); build(nd << 1 | 1, mid + 1, r);
pull(nd);
}
void go(int nd){
st[nd] = (sm[nd] - st[nd] + mod) % mod; lz[nd] ^= 1;
}
void push(int nd){
if(!lz[nd])return;
go(nd << 1); go(nd << 1 | 1);
lz[nd] = 0;
}
void upd(int nd, int l, int r, int ql, int qr){
if(ql > r || qr < l)return;
if(ql <= l && qr >= r){
go(nd);
return;
}
push(nd);
int mid = (l + r) >> 1;
upd(nd << 1, l, mid, ql, qr); upd(nd << 1 | 1, mid + 1, r, ql, qr);
pull(nd);
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N; m = M;
for(int i = 1; i < n + m; i++){
adj[P[i]].pb(i);
}
for(int i = 0; i < m; i++){
a[i] = A[i];
}
dfs(0); dfs2(0, 1);
build(1, 0, m - 1);
}
int count_ways(int L, int R) {
upd(1, 0, m - 1, L - n, R - n);
return(st[1]);
}
/*
//#include "circuit.h"
#include <cassert>
#include <cstdio>
#include <vector>
int main() {
int N, M, Q;
assert(3 == scanf("%d %d %d", &N, &M, &Q));
std::vector<int> P(N + M), A(M);
for (int i = 0; i < N + M; ++i) {
assert(1 == scanf("%d", &P[i]));
}
for (int j = 0; j < M; ++j) {
assert(1 == scanf("%d", &A[j]));
}
init(N, M, P, A);
for (int i = 0; i < Q; ++i) {
int L, R;
assert(2 == scanf("%d %d", &L, &R));
printf("%d\n", count_ways(L, R));
}
return 0;
}
*/
