Non‐Adjacent Monomino Tiling

ITX351 has a 2 × N rectangular road which he wants to tile. Originally he bought N bricks each of size 2 × 1. However, during transport one of these bricks broke into two pieces of size 1 × 1. Now, he plans to tile the entire road with the following conditions:

• The two 1 × 1 tiles must not be placed so that they share a common edge (i.e. they may not be adjacent horizontally or vertically).
• The remaining N-1 bricks, each of size 2 × 1 (which may be rotated so as to cover a 1 × 2 area), can be placed arbitrarily to complete the tiling.

All placements together must exactly cover the 2 × N board. Count the number of valid tilings.

In mathematical terms, if we label the board cells by their coordinates and use dominoes to refer to the 2 × 1 pieces, and monominoes to refer to the 1 × 1 pieces, then the two monomino cells must not be edge‐adjacent. All other placements (dominoes placed vertically or horizontally) are allowed.

Note: Any answer that computes the correct count will be accepted.

inputFormat

The input consists of a single line containing an integer N indicating the number of columns of the 2 × N board.

Constraints: 1 ≤ N ≤ 50 (for example).

outputFormat

Output a single integer – the number of valid tilings satisfying the conditions.

sample

1

0