Дикари, живущие на острове невезения умеют считать только до двух. Поэтому у них есть только две цифры - цифра 1 и цифра 2. Кроме того, дикари очень суеверные люди. Числа, в которых стоят подряд три одинаковые цифры, они считают несчастливыми и не используют. Например, число 1221212 можно использовать, так как в нем нет трех подряд идущих одинаковых цифр. А число 12121112 нельзя. В нем есть три подряд идущие цифры (в этом примере это единицы).

Вам следует выяснить, сколько существует n-значных чисел, состоящих только из цифр 1 и 2 таких, что в них нет трех подряд идущих одинаковых цифр.

Входные данные

Одно натуральное число n (1 ≤ n ≤ 30).

Выходные данные

Выведите количество n-значных чисел, состоящих из только из цифр 1 и 2, и не содержащих трех подряд идущих одинаковых цифр.