#include<bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define dbg(x) cout << (#x) << " : " << x << endl
#define pb push_back
#define all(x) x.begin(),x.end()
#define LOOP(n) for(int rp=0;rp<n;rp++)
#define sq(x) ((x)*(x))
typedef long long ll;
typedef long double dl;
const int SZ=5e5+7;
const ll INF=1e18+7;
const dl eps=1e-9;
int MOD=1e9+2022;
mt19937_64 rng(time(0));
int rnd(int l,int r){
    return uniform_int_distribution<int>(l,r)(rng);
}
ll trig(ll x){
    return x*(x+1)/2;
}
int getN(){
    int n;cin >> n;
    return n;
}
#define cmbntrcs fact[0]=1;for(int i=1;i<SZ;i++)fact[i]=mul(fact[i-1],i);finv[SZ-1]=inv(fact[SZ-1]);for(int i=SZ-2;i>0;i--)finv[i]=mul(finv[i+1],i+1);
int fact[SZ],finv[SZ];
int add(int x,int y,int MOD=MOD){
    x+=y;if(x>=MOD)x-=MOD;
    return x;
}
int sub(int x,int y,int MOD=MOD){
    x-=y;if(x<0)x+=MOD;
    return x;
}
int mul(int x,int y,int MOD=MOD){
    return(x*1ll*y)%MOD;
}
int pwr(int x,ll b,int MOD=MOD){
    int rt=1;
    while(b>0){
        if(b&1)rt=mul(rt,x,MOD);
        x=mul(x,x,MOD),b>>=1;
    }
    return rt;
}
int inv(int x,int MOD=MOD){
    return pwr(x,MOD-2,MOD);
}
#include "circuit.h"
//#include "stub.cpp"
int n,m,p[SZ],a[SZ],c[SZ],I[SZ];
vector<int>g[SZ],v;
int dp[1007][1007],N;
int solve(int i,int P){
    if(i==N)return(P?0:1);
    if(dp[i][P]!=-1)return dp[i][P];
    return dp[i][P]=add(mul(solve(i+1,P),sub(c[v[i]],a[v[i]])),mul(solve(i+1,(P?P-1:0)),a[v[i]]));
}
void calc(int i){
    v=g[i],N=sz(v);
    for(int i=0;i<=N;i++)for(int j=0;j<=N;j++)dp[i][j]=-1;
    a[i]=0;
    for(int P=1;P<=N;P++)a[i]=add(a[i],solve(0,P));
}
void init(int N,int M,vector<int>P,vector<int>A){
    n=N,m=M;
    for(int i=0;i<n+m;i++)p[i]=P[i],I[i]=0;
    for(int i=1;i<n+m;i++)g[p[i]].pb(i);
    for(int i=0;i<m;i++)a[i+n]=A[i],c[i+n]=1;
    for(int i=n-1;i>=0;i--){
        c[i]=sz(g[i]);
        for(auto&j:g[i])c[i]=mul(c[i],c[j]);
        calc(i);
    }
}
int prp(int i){
    for(int ch=i*2+1;ch<=i*2+2;ch++){
        if(I[i])a[ch]=sub(c[ch],a[ch]);
        I[ch]^=I[i];
    }
    I[i]=0;
}
void upd(int l,int r,int i=0,int lx=n,int rx=n+m-1){
    if(r<lx||rx<l)return;
    if(lx>=l&&rx<=r){
        I[i]^=1,a[i]=sub(c[i],a[i]);
        return;
    }
    prp(i);
    int md=(lx+rx)>>1;
    upd(l,r,i*2+1,lx,md),upd(l,r,i*2+2,md+1,rx);
    calc(i);
}
int count_ways(int l,int r){
    upd(l,r);
    return a[0];
}
/*int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    //cout << fixed << setprecision(12);
    int tt=1;
    //cin >> tt;
    LOOP(tt){
        //code
    }
    return 0;
}
*/