Дикуни, які живуть на острові невезіння вміють рахувати лише до двох. Тому у них є лише дві цифри — цифра 1 і цифра 2. Крім того, дикуни дуже забобонні люди. Числа, у яких стоять підряд три однакові цифры, вони вважають нещасливими і не використовують. Наприклад, число 1221212 можна використовувати, так як у ньому немає трьох підряд однакових цифр. А число 12121112 не можна. У ньому є три підряд однакові цифри (у цьому прикладі це одиниці).

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

Вхідні дані

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

Вихідні дані

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