No submission language available for this problem.

Background

Special for beginners, ^_^

Description

有一条高度为 1，长度为 n 的墙，有两类瓷砖可以铺在墙上。第一类是长度为 1 的正方形瓷砖，第二类是长度大于等于 3 的瓷砖。两块第二类瓷砖之间，至少要铺隔一块第一类瓷砖。问一共有多少种铺设的方案。

Format

Input

一个整数 n 表示墙的长度。

Output

一个整数表示铺设的方案总数。

Samples

3

2

6

11

12

189

Limitation

1 ≤ n ≤ 50