Гномы, жители страны мории, добывают драгоценные камни трех видов — поделочные (вид a), полудрагоценные (вид b) и драгоценные (вид c). хранят их гномы в одинаковых коробках, каждую из которых наполняют только одним видом камней. заполненные коробки гномы складывают в огромных залах мории одну на другую так, что получаются вертикальные стопки.

самые «плохие» стопки гномы оркам. стопка считается плохой, если в ней подряд лежат более одной коробки, заполненной камнями вида a. стопка считается «хорошей», если она не является «плохой».

от вас требуется написать программу, которая для заданного количества коробок n будет определять число возможных «хороших» стопок.

формат ввода
в единственной строке входного файла записано одно натуральное число 1 ≤ n ≤ 20.

формат вывода
в единственной строке входного файла записано одно натуральное число — количество «хороших» вариантов формирования стопки.

пример
ввод вывод
2 8

гуудик    3   05.12.2019 10:56    1