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

#define ff   first
#define ss   second
#define pb   push_back

const int MXN = 2e5+5;
const int mod = 1000002022;

int v[MXN];
int pot[MXN];
vector <int> g[MXN];
int sum0[MXN], sum1[MXN], lazy[MXN];
int subtree[MXN];
int n;
int m;
int a[MXN];

void build (int node, int l, int r) { 
  if (l == r) { 
    if (a[l] == 0) sum0[node] = v[l + n];
    else sum1[node] = v[l + n];
    return;
  }
  int m = (l + r) / 2;
  build (node * 2, l, m);
  build (node * 2 + 1, m + 1, r);
  sum0[node] = (sum0[node * 2] + sum0[node * 2 + 1])%mod;
  sum1[node] = (sum1[node * 2] + sum1[node * 2 + 1])%mod;
 // cout << "in build " << l << ' ' << r << ' ' << sum1[node] << '\n';
}

void propagate (int node) { 
  if (lazy[node]) { 
    swap(sum0[node], sum1[node]);
    lazy[node * 2] ^= 1;
    lazy[node * 2 + 1] ^= 1;
  }
  lazy[node] = 0;
}

void update (int node, int l, int r, int a, int b) {
  propagate(node);
  if (b < l || a > r) return;
  if (a <= l && r <= b) {
    lazy[node] = 1;
    propagate(node);
    return;
  }
  int m = (l + r) / 2;
  update(node * 2, l, m, a, b);
  update(node * 2 + 1, m + 1, r, a, b);
  sum0[node] = (sum0[node * 2] + sum0[node * 2 + 1])%mod;
  sum1[node] = (sum1[node * 2] + sum1[node * 2 + 1])%mod;
}

void dfs (int u) { 
  if (g[u].size()) subtree[u]++;
  for (auto &v : g[u]) { 
    dfs(v);
    subtree[u] += subtree[v];    
  }
}

void init(int N, int M, vector<int> P, vector<int> A) {
  n=N; m=M;
  pot[0]=1;
  for (int i = 1; i < MXN; ++i) pot[i] = (1ll * pot[i - 1] * 2) % mod;
  for (int i = 1; i < N + M; ++i) g[P[i]].pb(i);
  for (int i = 0; i < M; ++i) a[i] = A[i];
  dfs(0);
  v[0]=1;
  for (int i = 1; i < N + M; ++i) { 
    int ot = (g[P[i]][0] == i ? g[P[i]][1] : g[P[i]][0]);
    v[i] = (1ll * v[P[i]] * pot[subtree[ot]]) % mod;
    //cout << i << ' ' << v[i] << '\n';
  }
  build (1, 0, M-1);
}

int count_ways(int L, int R) {
  update(1, 0, m-1, L-n, R-n);
 // cout << sum1[1] << '\n';
  return sum1[1];
}