#include "circuit.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ll long long 
#pragma GCC optimize("trapv")

vector<int> a;  
int n , m;
vector<ll> dp[2000] , dp2;
vector<vector<int>> adj; 
vector<ll> pw; 
const int mod =  1000002022;

// dp[i] = number of ways to make i = 1; 





void dfs(int node){
  if (node >= n) {dp[0][node]= a[node-n]; dp2[node]=  1; return;}
  int c = adj[node].size();  
  dp2[node] = c;
  for (auto i : adj[node]){
    dfs(i);
    dp2[node]*=dp2[i];
    dp2[node]%=mod; 
  }
  ll sdp[c+1][c+1] = {};
  sdp[0][0] = 1;
  for (int i = 1 ; i <= c ; i++){
    for (int j = 1 ; j <= i ; j++){
      sdp[i][j] = sdp[i-1][j-1] * dp[0][adj[node][i-1]] + sdp[i-1][j] * (dp2[adj[node][i-1]] - dp[0][adj[node][i-1]] + mod)%mod;
      sdp[i][j] %= mod; 
    }
  }
  for (int i = 1 ; i <= c;  i++){
    dp[i-1][node] = sdp[c][i] ;
  }
  for (int j = c-2 ; j >= 0 ; j--) dp[j][node] += dp[j+1][node] , dp[j][node]%=mod; 
  for (int j = c-2 ; j >= 0 ; j--) dp[j][node] += dp[j+1][node] , dp[j][node]%=mod; 
}



void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  n= N,  m = M; a = A; 
  adj.assign(N+M , {});
  for (int i = 1 ; i < N + M ; i++) adj[P[i]].push_back(i);  
}

int count_ways(int L, int R) {
  for (int i = L ; i <= R ; i++) a[i-n] = (!a[i-n]);
  for (int i = 0 ; i < 2000 ; i++) dp[i].assign(n+m+1 , 0);
   dp2.assign(n+m+1 , 0); 
  dfs(0); 
  return dp[0][0]%mod; 
}