D. Почти плавные числа

Назовём число почти плавным, если любые две его соседние цифры различаются не более чем на два.

По данному $n$ определите количество почти плавных натуральных чисел длины ровно $n$. Ведущих нулей у числа нет.

Одна строка содержит число $n$ ($1 \le n \le 18$).

Одно число — количество почти плавных чисел.