#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);
  }
  for (int msk = 0 ; msk  < (1<<c) ; msk++){
    ll prod = 1; 
    for (int i = 0 ; i < c ; i++){
      if (msk & (1<<i)) prod*=(dp[0][adj[node][i]]); 
      else prod *= (dp2[adj[node][i]] - dp[0][adj[node][i]])%mod; 
    }
    dp[__builtin_popcountll(msk)-1][node] += prod;
    dp[__builtin_popcountll(msk)-1][node]  %= mod;  
  }
  for (int j = c-1 ; j >=0 ; j--){
    dp[j][node] += dp[j+1][node]; 
  }
  for (int j = c-1 ; j >= 0 ; j--){
    dp[j][node] += dp[j+1][node]; 
  }
}



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

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 < 1000 ; i++) dp[i].assign(n+m+1 , 0);
   dp2.assign(n+m+1 , 0); 
  dfs(0); 
  return dp[0][0]%mod; 
}