Знайдіть, скільки існує рядків заданої довжини $n$, які складаються лише з символів '$a$', '$b$' та '$c$', і які не містять підрядка "$ab$". \InputFile Єдине число $n~(0 \le n \le 45)$. \OutputFile Виведіть кількість шуканих рядків.