Background

Special for beginners, ^_^

Description

有 $1×n$ 的一个长方形，用一个 $1×1,1×2$ 和 $1×3$ 的骨牌铺满方格。例如当 $n=3$ 时为 $1×3$ 的方格。此时用 $1×1,1×2$ 和 $1×3$ 的骨牌铺满方格，共有四种铺法。如下图：

Format

Input

一个整数 $n\ (1\le n\le 36)$，表示 $1\times n$ 的长方形。

Output

一个整数，表示铺满给定长方形的方法数。

Samples

3

4

Limitation

1s, 1024KiB for each test case.