#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;
}

struct node {
  int sm, sm2;
  bool lz;
} t[(1 << 18)];

void prop(int l, int r, int x) {
  if (!t[x].lz)return;
  swap(t[x].sm, t[x].sm2);
  t[x*2+1].lz ^= 1;
  t[x*2+2].lz ^= 1;
  t[x].lz = false;
}

node merge(node &lef, node &rig) {
  return {
    ad(lef.sm, rig.sm),
    ad(lef.sm2, rig.sm2),
    0
  };
}

void build(int l, int r, int x) {
  if (l == r) {
    if (dp[l])t[x] = {contrib[l], 0, 0};
    else t[x] = {0, contrib[l], 0};
    return;
  }
  int md = (l + r) >> 1;
  build(l, md, x*2+1);
  build(md+1, r, x*2+2);
  t[x] = merge(t[x*2+1], t[x*2+2]);
}

void upd(int li, int ri, int x, int l, int r) {
  if (li >= l && ri <= r) {
    t[x].lz ^= 1;
    prop(li, ri, x);
    return;
  }
  prop(li, ri, x);
  if (li > r || ri < l)return;
  int md = (li + ri) >> 1;
  upd(li, md, x*2+1, l, r);
  upd(md+1, ri, x*2+2, l, r);
  t[x] = merge(t[x*2+1], t[x*2+2]);
}

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-N] = A[i-N];
      contrib[i-N] = contrib[i];
    }
    build(0, m-1, 0);
}

int count_ways(int L, int R) {
    L -= n;
    R -= n;
    upd(0, m-1, 0, L, R);
    return t[0].sm;
}