#include <bits/stdc++.h> using namespace std; const int MAXN=1e5+10; const int MOD=1000002022; int c[MAXN],n,m,s[MAXN],a[MAXN]; vector <int> g[MAXN]; void dfs (int node){ int aux=g[node].size(); s[node]=max (1,aux); for (auto x:g[node]){ dfs (x); s[node]=1LL*s[node]*s[x]%MOD; } } void solve (int node){ vector <int> dpp(g[node].size ()),dps(g[node].size ()); for (int i=0;i<g[node].size ();++i){ int x=g[node][i]; if (i==0) dpp[i]=s[x]; else dpp[i]=1LL*dpp[i-1]*s[x]; } for (int i=g[node].size ()-1;i>=0;--i){ int x=g[node][i]; if (i==g[node].size ()-1) dps[i]=s[x]; else dps[i]=1LL*dps[i+1]*s[x]; } for (int i=0;i<g[node].size ();++i){ int crt=c[node],x=g[node][i]; if (i!=0) crt=1LL*crt*dpp[i-1]%MOD; if (i!=g[node].size()-1) crt=1LL*crt*dps[i+1]%MOD; c[x]=crt; solve (x); } } struct AINT{ int aint[4*MAXN],lazy[4*MAXN],sum[4*MAXN]; void init (int node, int l, int r){ if (l==r){ sum[node]=c[l+n]; if (a[l]) aint[node]=sum[node]; else aint[node]=0; return; } int mij=(l+r)/2; init (2*node,l,mij); init (2*node+1,mij+1,r); sum[node]=(sum[2*node]+sum[2*node+1])%MOD; aint[node]=(aint[2*node]+aint[2*node+1])%MOD; } void lz (int node, int l, int r){ if (lazy[node]==0) return; aint[node]=(sum[node]-aint[node]+MOD)%MOD; if (l!=r){ lazy[2*node]^=lazy[node]; lazy[2*node+1]^=lazy[node]; } lazy[node]=0; } void update (int node, int l, int r, int ql, int qr){ lz (node,l,r); if (r<ql or l>qr) return; if (ql<=l and r<=qr){ lazy[node]^=1; lz (node,l,r); return; } int mij=(l+r)/2; update (2*node,l,mij,ql,qr); update (2*node+1,mij+1,r,ql,qr); aint[node]=(aint[2*node]+aint[2*node+1])%MOD; } void update (int l, int r){ l-=n; r-=n; update (1,0,m-1,l,r); } }v; void init (int N, int M, vector <int> p, vector <int> A){ n=N; m=M; for (int i=0;i<m;++i) a[i]=A[i]; for (int i=1;i<p.size ();++i){ g[p[i]].push_back (i); } dfs (0); c[0]=1; solve (0); v.init (1,0,m-1); } int count_ways (int l, int r){ v.update (l,r); return v.aint[1]; }