P3682寻路 | ||
|
问题描述
在平面坐标系上,我们要从原点(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后再输出!
样例输入 1
149
样例输出 1
97791968157406749394924901075381707518323470767341721197980700152917
样例输入 2
10
样例输出 2
2188
样例输入 3
4
样例输出 3
9
样例输入 4
3
样例输出 4
4