Description

There is a 1×n rectangular grid to be completely tiled using 1×1, 1×2, and 1×3 dominoes. For example, when n=3, it's a 1×3 grid. In this case, there are four ways to tile the grid using 1×1, 1×2, and 1×3 dominoes, as shown in the following figure:

Input Format

A positive integer n, representing a 1×n rectangular grid, where 0 < n <= 30.

Output Format

A number indicating the total number of tiling methods.

```input1 4 ``` ```output1 7 ``` ```markdown ## Source

CodesOnline