Tile Codes

A 2 x N board must be tiled completely using 1 x 2, 2 x 1, and 2 x 2 tiles. Each tiling is used as a code.

However, two tilings that become identical when the board is flipped left-to-right are considered the same code.

Given N, compute the number of distinct tile codes.

The first line contains the board length N (1 <= N <= 30).

Print the number of distinct tile codes.