J. Плавные числа

1000 мс · 256 МБ · всё или ничего

Натуральное число называется плавным, если значения соседних цифр отличаются не более чем на 1. Посчитайте количество $N$ -значных плавных чисел; запись не может начинаться с нуля.

Формат ввода

В единственной строке — число $N$ ( $1 \le N \le 20$ ).

Формат вывода

Выведите количество $N$ -значных плавных чисел.

Примеры

ввод

вывод

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.