# Numbers

# Numbers

Savages, living on the island of bad luck can only take up to two. Therefore they have only two digits - the number **1** and number **2**. In addition, the natives are very superstitious people. The numbers, which stand three consecutive identical numbers, they feel unhappy and do not use. For example, the number **1221212** can be used, since there are no three consecutive identical digits. And the number **12121112** can not. There are three consecutive numbers (in this example is one).

Your task is to find out how many there are **n**-digit numbers, consisting only of digits **1** and **2**, such that they do not have three consecutive identical digits.

#### Input

One integer **n** (**1** ≤ **n** ≤ **30**).

#### Output

Print the amount of **n**-digit numbers, consisting of only digits **1** and **2**, and do not contain three consecutive identical digits.

The only line of the input file contains integer

1

2

2

4

3

6