#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 , 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){
    int c = adj[node].size(); 
  if (node >= n) {dp[node] = a[node-n]; dp2[node]=  1; return;}
  dp2[node] = c;
  for (auto i : adj[node]){
    dfs(i);
    dp2[node]*=dp2[i];
    dp2[node]%=mod; 
  }
  vector<int> a(c) , b(c);
  for (int i = 0 ; i < c ; i++){
    a[i] = dp[adj[node][i]]; 
    b[i] = (dp2[adj[node][i]] - a[i] + mod)%mod; 
  }
  // for (int msk = 1 ; msk  < (1<<c) ; msk++){
  //   ll prod = 1; 
  //   for (int i = 0 ; i < c ; i++){
  //     if (msk & (1<<i)) prod*=a[i];
  //     else prod *= b[i];  
  //     prod %= mod; 
  // }  
  //   int x = __builtin_popcount(msk); 
  //   dp[node] += prod * x;
  //   dp[node]  %= mod;  
  // }

  ll sdp[c+1][c+1] = {};
  sdp[0][0] = 1; 
  for (int i = 1;  i <= c ; i++){
    for (int j = 0 ; j <= i ; j++){
      sdp[i][j] += ( j ? sdp[i-1][j-1] * a[i-1] : 0) + sdp[i-1][j] * b[i-1]; 
      sdp[i][j] %= mod; 
    }
  }
  for (int i = 1;  i <= c;  i++){
    dp[node] += sdp[c][i] * i; 
  }
}



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