Гномы, жители страны мории, добывают драгоценные камни трех видов — поделочные (вид a), полудрагоценные (вид b) и драгоценные (вид c). хранят их гномы в одинаковых коробках, каждую из которых наполняют только одним видом камней. заполненные коробки гномы складывают в огромных залах мории одну на другую так, что получаются вертикальные стопки.
самые «плохие» стопки гномы оркам. стопка считается плохой, если в ней подряд лежат более одной коробки, заполненной камнями вида a. стопка считается «хорошей», если она не является «плохой».
от вас требуется написать программу, которая для заданного количества коробок n будет определять число возможных «хороших» стопок.
формат ввода
в единственной строке входного файла записано одно натуральное число 1 ≤ n ≤ 20.
формат вывода
в единственной строке входного файла записано одно натуральное число — количество «хороших» вариантов формирования стопки.
пример
ввод вывод
2 8
