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.
The input consists of multiple test cases. Each test case contains only one integer n (3 ≤ n ≤ 104). Process util EOF is met.
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