#include "circuit.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=2e5+5,mod=1e9+2022;

int N,M;
vector<int> adj[MX];
vector<int> A;

ll dp[MX][2];

void dfs(int v) {
        if(adj[v].empty()) {
                dp[v][A[v-N]]=1;
                return;
        }

        for(auto u:adj[v]) {
                dfs(u);
        }

        int s=adj[v].size();
        vector<ll> f(s+1);
        f[0]=1;

        for(auto u:adj[v]) {
                vector<ll> nxt(s+1);
                for(int i=0;i<=s;i++) {
                        nxt[i+0]+=f[i]*dp[u][0]%mod;
                        nxt[i+0]%=mod;
                        if(i==s) continue;
                        nxt[i+1]+=f[i]*dp[u][1]%mod;
                        nxt[i+1]%=mod;
                }
                swap(nxt,f);
        }

        ll ls=0,rs=0;
        for(int p=0;p<=s;p++) {
                rs+=f[p];
                rs%=mod;
        }

        for(int p=0;p<=s;p++) {
                if(p>0) {
                        dp[v][1]+=rs;
                        dp[v][1]%=mod;
                        dp[v][0]+=ls;
                        dp[v][0]%=mod;
                }

                ls+=f[p];
                ls%=mod;

                rs-=f[p];
                rs+=mod;
                rs%=mod;
        }
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
        ::N=N, ::M=M, ::A=A;

        for(int i=1;i<N+M;i++) {
                adj[P[i]].push_back(i);
        }
}

int count_ways(int L, int R) {
        L-=N,R-=N;
        for(int i=L;i<=R;i++) A[i]^=1;

        for(int i=0;i<N+M;i++) {
                dp[i][0]=dp[i][1]=0;
        }

        dfs(0);
        return dp[0][1];
}