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