#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[1001] , 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; 
  }
  for (int msk = 1 ; 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)%mod; 
      prod %= mod; 
    }
    int x = __builtin_popcount(msk) - 1; 
    dp[x][node] += prod;
    dp[x][node]  %= mod;  
  }
  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 <= 1000 ; i++) dp[i].assign(n+m+1 , 0);
   dp2.assign(n+m+1 , 0); 
  dfs(0); 
  return dp[0][0]%mod; 
}