#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;


long long int *t;

 inline long long int* at(int x, int y, int z, int w){
    return t+x*(405*6*201)+y*(6*201)+z*6+w;
}

long long int calculate(int x, int y, int z, int w){
    if(abs(x)>200 || abs(y)>200 || w>200) return 0;
    if(x==0 && y==0 &&z==0 && w==200) return 1;
    long long int s;
    if(*at(x+203,y+203,z,w)==-1){
        switch(z){
            case 0:
                s=calculate(x+1,y+1,5,w+1)+calculate(x+1,y+1,1,w+1);
                break;
            case 1:
                s=calculate(x+2,y,0,w+1)+calculate(x+2,y,2,w+1);
                break;
            case 2:
                s=calculate(x+1,y-1,1,w+1)+calculate(x+1,y-1,3,w+1);
                break;
            case 3:
                s=calculate(x-1,y-1,2,w+1)+calculate(x+1,y+1,4,w+1);
                break;
            case 4:
                s=calculate(x-1,y,3,w+1)+calculate(x-1,y,5,w+1);
                break;
            default:
                s=calculate(x-1,y+1,4,w+1)+calculate(x-1,y+1,0,w+1);
                break;
        }
        *at(x+203,y+203,z,w)=s%123456789;
    }
    return *at(x+203,y+203,z,w);
}


int main(){
    t = new long long int[405*405*6*201];
    for(long long int i=0;i<405*405*6*201;++i){
        t[i]=-1;
    }

    printf("%lld\n",calculate(0,0,0,0));
    system("pause");
    return 0;
}