Вася забыл свой пароль. Всё, что он помнит — что пароль имел длину $$$n$$$ и состоял только из цифр, причём любые две рядом стоящие цифры отличались не более чем на один.
Определите, сколько вариантов паролей придётся перебрать Васе при входе в систему, если нужный пароль ему попадётся в самом конце.
Вводится одно целое число $$$n$$$ ($$$2 \le n \le 25$$$) — длина пароля.
Выведите одно целое число — количество возможных паролей длины $$$n$$$.
Подзадача 1 (до 40 баллов): $$$n \le 10$$$
Подзадача 2 (до 60 баллов): $$$n \le 25$$$
2
28
