#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<ll,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1000002022;
int n,m;
vi a,p,ch;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n=N;m=M;a=A;p=P;
ch.resize(n+m,0);
REP(i,1,n+m)ch[p[i]]++;
return;
}
int count_ways(int L, int R) {
vector<vector<ll>> dp(n+m,vector<ll>(n+m,0)),dp2(n+m,vector<ll>(2,0));
REP(i,L-n,R-n+1)a[i]=1-a[i];
REP(i,n,n+m)dp2[i][a[i-n]]++;
REP(i,0,n)dp[i][0]=1;
for(int i=n+m-1;i>=0;i--){
int x=ch[i];
vector<ll> b=dp[i],c=dp[i];
REP(j,1,x+1){
b[j]+=b[j-1];
b[j]%=M;
}
for(int j=x-1;j>=0;j--){
c[j]+=c[j+1];
c[j]%=M;
}
REP(j,0,x+1){
if(j!=0)dp2[i][1]+=c[j];
if(j!=x)dp2[i][0]+=b[j];
dp2[i][1]%=M;
dp2[i][0]%=M;
}
if(i==0)break;
int k=p[i];
for(int j=n+m-1;j>=0;j--){
if(j!=n+m-1){
dp[k][j+1]+=dp[k][j]*dp2[i][1];
dp[k][j+1]%=M;
}
dp[k][j]*=dp2[i][0];
dp[k][j]%=M;
}
}
return (int)dp2[0][1];
}
