#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
typedef long long ll;
const int NN = 2e5+5, mod = 1000002022;
int n, m, dp[NN], tot[NN], dp2[NN], contrib[NN], tmp[NN], id[NN];
vector<int> pref[NN], suf[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 x = 1;
  pref[u].clear();
  suf[u].clear();
  for (int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
    id[v] = i;
    x = mul(x, tot[v]);
    pref[u].push_back(x);
  }
  x = 1;
  for (int i = adj[u].size()-1; i >= 0; i--) {
    int v = adj[u][i];
    x = mul(x, tot[v]);
    suf[u].push_back(x);
  }
  reverse(suf[u].begin(), suf[u].end());
}

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


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

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; i < N+M; i++) {
      int cur = i;
      dp[i] = 1;
      while (cur) {
        int pr = P[cur];
        int lef = 1, rig = 1;
        if (id[cur])lef = pref[pr][id[cur]-1];
        if (id[cur] != adj[pr].size()-1)rig = suf[pr][id[cur]+1];
        dp[pr] = mul(dp[cur], mul(lef, rig));
        cur = pr;
      }
      contrib[i] = dp[0];
      cur = i;
      while (~cur) {
        dp[cur] = 0;
        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;
}