#include <bits/stdc++.h>
//#include "stub.cpp"
#include "circuit.h"
using namespace std;
typedef long long ll;
const int NN = 1e5+5, mod = 1000002022;
int n, m, dp[NN], tot[NN], dp2[NN], contrib[NN], tmp[NN];
vector<int> adj[NN];

int ad(int x, int y) {
    x += y;
    return (x >= mod ? x - mod : x);
}

int sub(int x, int y) {
   x -= y;
   return (x < 0 ? x + mod : x);
}

int mul(ll x, ll y) {
  return (x * y) % mod;
}

void init_tot(int u) {
  for (auto &v : adj[u]) {
    init_tot(v);
    tot[u] = mul(tot[u], tot[v]);
  }
}

int on(int u) {
  return dp[u];
}


int zer(int u) {
  return sub(tot[u], dp[u]);
}

void calc(int u) {
  if (adj[u].empty())return;
  for (int i = 1; i <= adj[u].size(); i++) {
    dp2[i] = 0;
  }
  dp2[0] = 1;
  int ctr = 1;
  for (auto &v : adj[u]) {
    int zerr = zer(v), onn = on(v);
    for (int j = ctr; j >= 1; j--) {
      dp2[j] = ad(mul(dp2[j], zerr), mul(dp2[j-1], onn));
    }
    ctr++;
    dp2[0] = mul(dp2[0], zerr);
  }
  dp[u] = 0;
  int sm = 0;
  for (int j = adj[u].size(); j >= 1; j--) {
    sm = ad(sm, dp2[j]);
    dp[u] = ad(dp[u], sm);
  }
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
     n = N;
     m = M;
    for (int i = 0; i < N; i++) {
        adj[i].clear();
    }
    for (int i = 1; i < N + M; i++) {
        adj[P[i]].push_back(i);
    }
    for (int i = 0; i < N; i++) {
      tot[i] = adj[i].size();
    }
    for (int i = N; i < N + M; i++) {
        //dp[i] = A[i-N];
        dp[i] = 0;
        tot[i] = 1;
    }
    init_tot(0);
    for (int i = N-1; i >= 0; i--) {
      calc(i);
    }
    for (int i = N; i < N+M; i++) {
      dp[i] = 1;
      int cur = P[i];
      while (~cur) {
        tmp[cur] = dp[cur];
        calc(cur);
        cur = P[cur];
      }
      contrib[i] = dp[0];
      dp[i] = 0;
      cur = P[i];
      while (~cur) {
        dp[cur] = tmp[cur];
        cur = P[cur];
      }
    }
    for (int i = N; i < N+M; i++) {
      dp[i] = A[i-N];
    }
}

int count_ways(int L, int R) {
    for (int i = L; i <= R; i++) {
        dp[i] ^= 1;
    }
    int ans = 0;
    for (int i = n; i < n+m; i++) {
      ans = ad(ans, mul(dp[i], contrib[i]));
    }
    return ans;
}