#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x << ' '; print(x); cerr << endl;
#else
#define dbg(x)
#endif
void print(int x) {cerr << x;}
void print(long long x) {cerr << x;}
void print(char x) {cerr << x;}
void print(string x) {cerr << x;}
void print(double x) {cerr << x;}
template <class T> void print(vector <T> x);
template <class T> void print(set <T> x);
template <class T> void print(multiset <T> x);
template <class T, class V> void print(pair <T, V> x);
template <class T, class V> void print(map <T, V> x);
template <class T> void print(vector <T> x) {cerr << "[ "; for(auto i : x) {print(i); cerr << ' ';} cerr << "]";}
template <class T> void print(set <T> x) {cerr << "[ "; for(auto i : x) {print(i); cerr << ' ';} cerr << "]";}
template <class T> void print(multiset <T> x) {cerr << "[ "; for(auto i : x) {print(i); cerr << ' ';} cerr << "]";}
template <class T, class V> void print(pair <T, V> x) {cerr << "{"; print(x.first); cerr << ' '; print(x.second); cerr << "}";}
template <class T, class V> void print(map <T, V> x) {cerr << "[ "; for(auto i : x) {print(i); cerr << ' ';} cerr << "]";}
#define ll long long
#define pb push_back
#define ppb pop_back
#define PII pair <int, int>
#define PLL pair <ll, ll>
#define all(v) (v).begin(), (v).end()
#define OK cerr << "OK\n";
#define MP make_pair
const ll mod = 1000002022;
const int NN = 3e5 + 5;
vector <int> T[NN];
vector <int> p, a;
int n, m;
ll gorcakic[NN], allCases[NN];
vector <ll> pref, suff;
void calc_allCases(int node){
if(T[node].empty()){
allCases[node] = 1;
return;
}
int sz = T[node].size();
for(int i = 0; i < sz; i++){
int u = T[node][i];
calc_allCases(u);
}
pref.clear(); pref.resize(sz + 2);
suff.clear(); suff.resize(sz + 2);
pref[0] = suff[sz + 1] = 1;
for(int i = 0; i < sz; i++){
int u = T[node][i];
pref[i + 1] = pref[i] * allCases[u];
pref[i + 1] %= mod;
}
for(int i = sz - 1; i >= 0; i--){
int u = T[node][i];
suff[i + 1] = suff[i + 2] * allCases[u];
suff[i + 1] %= mod;
}
allCases[node] = sz * pref[sz];
allCases[node] %= mod;
}
void dfs(int node, ll tomultiply){
if(T[node].empty()){
gorcakic[node] = tomultiply;
return;
}
int sz = T[node].size();
pref.clear(); pref.resize(sz + 2);
suff.clear(); suff.resize(sz + 2);
pref[0] = suff[sz + 1] = 1;
for(int i = 0; i < sz; i++){
int u = T[node][i];
pref[i + 1] = pref[i] * allCases[u];
pref[i + 1] %= mod;
}
for(int i = sz - 1; i >= 0; i--){
int u = T[node][i];
suff[i + 1] = suff[i + 2] * allCases[u];
suff[i + 1] %= mod;
}
vector <ll> val(sz);
for(int i = 0; i < sz; i++){
val[i] = pref[i] * suff[i + 2];
val[i] %= mod;
val[i] *= tomultiply;
val[i] %= mod;
}
for(int i = 0; i < sz; i++){
dfs(T[node][i], val[i]);
}
}
struct segtree{
int sz = 1;
pair <ll, int> tree[4 * NN];
ll sum[NN];
void init(){
while(sz < m) sz <<= 1;
sum[0] = 0;
for(int i = 1; i <= m; i++){
sum[i] = sum[i - 1] + gorcakic[i + n - 1];
sum[i] %= mod;
}
build(0, 0, sz);
}
void build(int x, int lx, int rx){
if(rx == lx + 1){
tree[x].first = a[lx] * gorcakic[lx + n];
tree[x].first %= mod;
tree[x].second = 0;
return;
}
int mx = (lx + rx) / 2;
build(2 * x + 1, lx, mx);
build(2 * x + 2, mx, rx);
tree[x].first = tree[2 * x + 1].first + tree[2 * x + 2].first;
tree[x].first %= mod;
tree[x].second = 0;
}
void propagate(int x, int lx, int rx){
if(rx == lx + 1 || tree[x].second % 2 == 0) return;
int mx = (lx + rx) / 2;
tree[2 * x + 1].second += tree[x].second;
tree[2 * x + 2].second += tree[x].second;
tree[x].second = 0;
tree[2 * x + 1].first = (sum[mx] - sum[lx]) - tree[2 * x + 1].first; tree[2 * x + 1].first %= mod;
tree[2 * x + 2].first = (sum[rx] - sum[mx]) - tree[2 * x + 2].first; tree[2 * x + 2].first %= mod;
}
void upd(int l, int r){
upd(l, r, 0, 0, sz);
}
void upd(int l, int r, int x, int lx, int rx){
propagate(x, lx, rx);
if(lx >= r || rx <= l) return;
if(lx >= l && rx <= r){
tree[x].first = (sum[rx] - sum[lx]) - tree[x].first;
tree[x].first %= mod;
tree[x].second = 1;
return;
}
int mx = (lx + rx) / 2;
upd(l, r, 2 * x + 1, lx, mx);
upd(l, r, 2 * x + 2, mx, rx);
tree[x].first = tree[2 * x + 1].first + tree[2 * x + 2].first;
tree[x].first %= mod;
}
} st;
void init(int N, int M, std::vector<int> P, std::vector<int> A){
n = N, m = M, p = P, a = A;
for(int i = 1; i < n + m; i++){
T[p[i]].pb(i);
}
calc_allCases(0);
dfs(0, 1);
st.init();
}
int count_ways(int L, int R){
st.upd(L - n, R - n + 1);
return (st.tree[0].first + mod) % mod;
}
