本来想搞dp的，不过发现几乎无法达到。
无奈中，突发奇想：可以用数学。

如果意识到了其实没有几种“本质不同”的路线，那么就离AC不远了。

其实，可以枚举到达目的地时的方向，
再枚举绕圈的数量，最后排列组合一下，就OK了。
如果不耐心计算，WA是没的说的。

具体的公式可以看代码吧：
void MultiC(int &r,int a,int b){
	r=int(((long long)r*(long long)C[a][b])%(long long)MODULO);
}
void Calc(int &r,int a,int aa,int b,int bb,int c,int cc,int d,int dd){
	int t;
	t=1;
	MultiC(t,aa,a);
	MultiC(t,bb,b);
	MultiC(t,cc,c);
	MultiC(t,dd,d);
	r=(r+t)%MODULO;
}
ret=0;
//down
for (int i=0;i<=x-1 && i<=X-x && i<=y && i+1<=Y-y;i++)
Calc(ret,i,x-1,i,X-x,i,y,i+1,Y-y);
//right
for (int i=0;i<=x-1 && i<=X-x && i<=y && i<=Y-y;i++)
Calc(ret,i,x-1,i,X-x,i,y,i,Y-y);
//up
for (int i=0;i<=x-1 && i+1<=X-x && i+1<=y && i+1<=Y-y;i++)
Calc(ret,i,x-1,i+1,X-x,i+1,y,i+1,Y-y);
//left
for (int i=0;i<=x-1 && i+1<=X-x && i<=y && i+1<=Y-y;i++)
Calc(ret,i,x-1,i+1,X-x,i,y,i+1,Y-y);
if (y && !x)ret=(ret+1)%MODULO;
if (!y && !x)ret=(ret+1)%MODULO;
printf("%d\n",ret);