Tiling a 2×N Wall

We are given a wall of size (2 \times N). There are two types of tiles available in unlimited supply:

1. A domino of size (2 \times 1) (which can be rotated to become (1 \times 2)).
2. An L–shaped tromino covering 3 unit cells. One representative shape (which can be rotated) is shown below:

0  0
0  00

The task is to count the number of ways to completely cover the (2\times N) wall using these two kinds of tiles. Note that the tiles may be rotated arbitrarily and can be mixed. For example, a (2\times3) wall has 5 valid tilings. For a (2\times13) wall the total number of tilings is 13465; however, you are only required to output the last four digits if the answer has at least 4 digits. In this example, the output should be 3465. If the answer has fewer than 4 digits, output it directly without adding any leading zeros.

The tilings can be counted by using a state dynamic programming approach. If we denote by (A(n)) the number of tilings for a (2\times n) wall (with no pending cells to fill in the current column) and define extra states representing partially filled columns, one may derive the following recurrences:

• Let the four states for a column be defined by a bitmask for the two cells (bit0 for the top cell, bit1 for the bottom cell). We denote:
  • (A(n)): state 0 (both cells empty) for column n (i.e. no pending filling).
  • (B(n)): state 1 (top filled, bottom empty).
  • (C(n)): state 2 (bottom filled, top empty).
  • (D(n)): state 3 (both cells filled, which immediately transfers to the next column as state 0).

With base conditions

[ A(0)=1, \quad B(0)=0, \quad C(0)=0, \quad D(0)=0 ]

one may show that for (n\ge 1):

[ \begin{array}{rcl} A(n) &=& A(n-1) + D(n-1) + B(n-1) + C(n-1)\[1mm] B(n) &=& C(n-1) + D(n-1)\[1mm] C(n) &=& B(n-1) + D(n-1)\[1mm] D(n) &=& A(n-1). \end{array} ]

Then the answer for a (2\times N) wall is (A(N)). Finally, if (A(N)) has four or more digits (i.e. (A(N) \ge 1000)), output the last four digits (i.e. (A(N) \bmod 10000)); otherwise output (A(N)) itself.

You are to write a program to perform the above computation.

inputFormat

The input consists of a single integer (N) ((1 \le N \le 10^4) for example) representing the length of the wall (so the wall size is (2\times N)).

outputFormat

Output a single integer: if the total number of tilings has at least 4 digits, output the last 4 digits (without leading zeros); otherwise, output the number itself.

sample

1

1