# The Number of Paths

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

## Description

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.

## Input

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).

## Output

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

## Sample Input

1
2

## Sample Output

3
7

lcy