The Number of Paths

Let f (n) be the number of paths with n steps starting from O (0, 0), with steps of the type (1, 0), or (-1, 0), or (0, 1), and never intersecting themselves. For instance, f (2) =7, as shown in Fig.1. Equivalently, letting E=(1,0),W=(-1,0),N=(0,1), we want the number of words A1A2...An, each Ai either E, W, or N, such that EW and WE never appear as factors.

There are multiple cases in this problem and ended by the EOF. In each case, there is only one integer n means the number of steps(1<=n<=1000).

For each test case, there is only one integer means the number of paths.

1
2

3
7

SmallBeer (CML)

杭电ACM集训队训练赛（VIII）