eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Linguist

Linguist

Лимит времени 0.1 секунд
Лимит использования памяти 64 MiB

Марися, на відміну від Степана, навчається на лінгвістичному факультеті РуНУ, і, очевидно, не дуже полюбляє математику і все, що з нею пов’язано. Вона, як і усі студенти факультету, панічно боїться чисел, в яких модуль різниці будь-яких двох сусідніх цифр більше ніж 1 (такі дивні ці мовознавці).

Степану вкрай необхідно знайти всі числа, які він може використовувати, щоби не зашкодити психологічному стану Марисі. Але часу до їх зустрічі залишилося зовсім мало, порахуйте хоча б кількість N-значних додатніх цілих чисел, які Степан зможе використовувати при зустрічі з Марисею.

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

В єдиному рядку записано число N (1 ≤ N ≤ 20).

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

В єдиному рядку виведіть кількість N-значних додатніх чисел, які Степан сміливо зможе використовувати при зустічі з Марисею, не завдавши при цьому ніякої моральної шкоди.

Пример

Входные данные #1
1
Выходные данные #1
9
Источник ACM-ICPC Ukraine 2014, Перший етап, 26 квітня 2014 року