#include <fstream>
#include <queue>
using namespace std;

#define F stdin
ofstream G("bridge.out");

const int Nmax = 4005;
const int Steps = 4000;

const int Mod = 666013;

int D[Nmax][Nmax],N,M;
int A[Nmax],Next[Nmax];

queue<int> Q;
int x,k;

const int Buffer=1<<13;
char Buff[Buffer]; int Nxt=0;

int GetInt()
{
    int Nbr=0;
    while( Buff[Nxt]<'0' || '9'<Buff[Nxt] )
        if ( ++Nxt >= Buffer ) fread(Buff,Buffer,1,F), Nxt=0;
    while ( '0'<=Buff[Nxt] && Buff[Nxt]<='9' )
    {
        Nbr=Nbr*10+Buff[Nxt]-'0';
        if ( ++Nxt >= Buffer ) fread(Buff,Buffer,1,F), Nxt=0;
    }
    return Nbr;
}

int main()
{
    freopen("bridge.in","r",stdin);
    N=GetInt(),M=GetInt();
    for (int i=1;i<=N;++i)
    {
        A[i]=GetInt();
        if ( A[i] == 3 ) Q.push( i );
    }
    for ( ; Q.size() ; Q.pop() )
        Next[Q.front()]=GetInt();

    D[0][0]=1;
    for (int j=1;j<=Steps;++j)
    {
        D[j][1] = A[1]!=2 && ( j==1 || A[1]!=3 ) ? 1 : 0;
        D[j+1][Next[1]] += D[j][1];
        if ( A[Next[1]] != 0 && A[Next[1]] != 3 && A[1]==3 ) D[j+1][Next[1]]-=D[j][1], D[j][1]=0;
        D[j][Next[1]] %= Mod;
        if ( A[2] != 2 )
        {
            D[j][2] += A[2]!=3 ? D[j-1][2] : 0;
            D[j][2] += ( A[1]!=3 ) ? D[j-1][1] : 0;
            D[j][2] += ( A[2]!=1 && j==1 ) ? 1 : 0;
        }
        D[j][2] %= Mod;
        D[j+1][Next[2]] += D[j][2];
        if ( A[Next[2]] != 0 && A[Next[2]] != 3 && A[2]==3 ) D[j+1][Next[2]]-=D[j][2], D[j][2]=0;
        D[j][Next[2]] %= Mod;
        for (int i=3;i<=N;++i)
        {
            if ( A[i] != 2 )
            {
                D[j][i] += A[i]!=3 ? D[j-1][i] : 0;
                D[j][i] += ( A[i-1]!=3 ) ? D[j-1][i-1] : 0;
                D[j][i] += ( A[i]!=1 && A[i-2]!=3 ) ? D[j-1][i-2] : 0;
            }
            D[j][i] %= Mod;
            D[j+1][Next[i]] += D[j][i];
            if ( A[Next[i]] != 0 && A[Next[i]] != 3 && A[i]==3 ) D[j+1][Next[i]]-=D[j][i] , D[j][i]=0;
            D[j][Next[i]] %= Mod;
        }
    }

    for ( int i=1;i<=M;++i )
    {
        x=GetInt(),k=GetInt();
        G<<D[k][x]<<'\n';
    }

    fclose(stdin);
    G.close();

    return 0;
}