在平面坐标系上，我们要从原点(0,0)走到点(n,0)。
每一步，我们可以按下列方式行走，假设现在我们位于点(x,y):
1.往右走一步，到达点(x+1,y)
2.往右上走一步,到达点(x+1,y+1)
3.往右下走一步，到达点(x+1,y-1)
行走的过程中，要求经过的点的y坐标必须>=0。
问，从起点到终点，恰好走n步，总的方案数是多少？
如下图所示，n=4时，共9种方案

一行，一个整数n，表示终点坐标为(n,0),2 < n <= 1000

一行，一个整数，表示所求结果。注意，结果可能很大，mod 10^100后再输出！