#include "circuit.h"

#include <vector>
#include<bits/stdc++.h>

namespace Sol{

using namespace std;
using ll=long long;
using u64=unsigned long long;
//using lll=__int128_t;
using lf=long double;
using Pr=pair<int,int>;
#define F(i,l,r) for(ll i=l;i<=ll(r);++i)
#define G(i,r,l) for(ll i=r;i>=ll(l);--i)
#define ct const
#define il inline
#define pb push_back
#define fi first
#define se second
#define mkr make_pair
template<class T>
il void tomn(T&x,T ct&y){y<x?x=y,0:0;}
template<class T>
il void tomx(T&x,T ct&y){x<y?x=y,0:0;}
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define CUT dbg("===================\n")
ct lf EPS=1e-10L;
il int dcmp(lf x){return fabs(x)<=EPS?0:(x<0?-1:1);}
ct ll INF=4e18L;
//ct int INF=1.02e9;
//il void rd(int&x){scanf("%d",&x);}
//il void rd(ll&x){scanf("%lld",&x);}

ct ll P=1000002022;
void add2(ll&x,ll y){x+=y,x-=((-(x>=P))&P);}
void sub2(ll&x,ll y){x-=y,x+=((-(x<0))&P);}
ll add(ll x,ll y){return add2(x,y),x;}
ll sub(ll x,ll y){return sub2(x,y),x;}

ct int N=4.02e5;

struct D{ll s,x;};
D operator*(D x,D y){return D{x.s+y.s,x.x+y.x};}
class SGT{
	struct Node{ll s,x;int tg;}d[4*N];
#define L (p<<1)
#define R (L|1)
	void up(int p){
		d[p].x=add(d[L].x,d[R].x);
	}
	void upd(int p){d[p].x=sub(d[p].s,d[p].x),d[p].tg^=1;}
	void push(int p){
		if(d[p].tg)upd(L),upd(R),d[p].tg=0;
	}
	int l,r;
	void upd(int p,int s,int t){
		if(l<=s&&t<=r)return upd(p);
		int mid=(s+t)>>1;push(p);
		if(l<=mid)upd(L,s,mid);
		if(mid<r)upd(R,mid+1,t);
		up(p);
	}
	void build(int p,int s,int t,ll*a,int*b){
		d[p].tg=0;
		if(s==t){
//			dbg("%d:	%lld	%lld\n",s,a[s],b[s]*a[s]);
			return d[p]=Node{a[s],b[s]*a[s]},void();
		}
		int mid=(s+t)>>1;
		build(L,s,mid,a,b);
		build(R,mid+1,t,a,b);
		d[p].s=add(d[L].s,d[R].s);
//		d[p].s=d[L].s+d[R].s;
		up(p);
	}
public:
	int n;
	void build(int n_,ll*a,int*b){build(1,1,n=n_,a,b);}
	void upd(int l_,int r_){
		l=l_,r=r_,upd(1,1,n);
	}
	ll qry(){return d[1].x;}
#undef L
#undef R
}sgt;

int n,m,fa[N],a[N];
ll f[N],g[N];
vector<int>t[N];
void dfs(int u){
	int n=t[u].size();
	vector<ll>pre(n,1),suf(n,1);
	F(i,0,n-2)pre[i+1]=pre[i]*g[t[u][i]];
	G(i,n-1,1)suf[i-1]=suf[i]*g[t[u][i]];
	F(i,0,n-1)
		f[t[u][i]]=f[u]*pre[i]%P*suf[i]%P,dfs(t[u][i]);
}
void init(){
	F(i,1,n+m)f[i]=g[i]=1,t[fa[i]].pb(i);
	G(i,n,1)(g[i]*=t[i].size())%=P,(g[fa[i]]*=g[i])%=P;
	dfs(1);
	
//	dbg("fa:	");
//	F(i,1,n+m)dbg("%d ",fa[i]);
//	dbg("\n");
//	dbg("g:	");
//	F(i,1,n+m)dbg("%lld ",g[i]);
//	dbg("\n");
//	dbg("f:	");
//	F(i,1,n+m)dbg("%lld ",f[i]);
//	dbg("\n");
//	dbg("a:	");
//	F(i,1,m)dbg("%d ",a[i]);
//	dbg("\n");
	
	sgt.build(m,f+n,a);
}
ll qry(int l,int r){
	return sgt.upd(l-n,r-n),sgt.qry();
}

}//namespace Sol

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	using namespace Sol;
	n=N,m=M;
	F(i,1,n+m)fa[i]=P[i-1]+1;
	F(i,1,m)a[i]=A[i-1];
	init();
}

int count_ways(int L, int R) {
  return Sol::qry(L+1,R+1);
}