Description

Given a square of size n + 2 with a square hole of size n − 2 in the middle (see the figure below), calculate the number of different ways to tile it with dominoes of size 1 × 2.

Input

The input consists of multiple test cases. Each test case contains only one integer n (3 ≤ n ≤ 10⁴). Process util EOF is met.

Output

For each test case, output the desired number in decimal using the comma as the thousand separator.

3
50

196
401,520,777,816,387,690,468,975,409,805,843,797,460,004

Source

POJ Founder Monthly Contest – 2007.12.30, frkstyc