Domino Tiling

Problem Background

Special for beginners, ^_^

Problem Description

There is a $1 \times n$ rectangle. We want to tile it completely using $1 \times 1$, $1 \times 2$, and $1 \times 3$ dominoes. For example, when $n=3$ it is a $1 \times 3$ rectangle. At this time, tiling it with $1 \times 1$, $1 \times 2$, and $1 \times 3$ dominoes gives four tiling methods, as shown in the figure below:

Input Format

An integer $n\ (1\le n\le 36)$, representing the $1\times n$ rectangle.

Output Format

One integer, the number of ways to tile the given rectangle.

Sample Input 1

3

Sample Output 1

4

Constraints

1s, 1024KiB for each test case.