Дороги
С древних времен Россия (как оказывается, не только она) известна своими плохими дорогами. Однако, начиная с послезавтрашнего дня, эта проблема будет решена! Министерство Путей Сообщения Менделеево (и не только его) разработало новую реформу, призванную значительно улучшить качество дорог. Реформа звучит следующим образом:
Каждая строящаяся дорога состоит из n сегментов шириной 1 метр.
Каждый сегмент имеет целую высоту от 0 до 9 метров над уровнем моря.
Разница в высоте между двумя последовательными сегментами не должна быть больше 1 метра (то есть каждый следующий сегмент должен быть выше предыдущего на -1, 0 или 1 метр).
Миллионы отечественных автолюбителей уже ликуют, восхищенные новой реформой. Единственный вопрос, который их волнует - сколько различных дорог длины n можно построить таким образом? Дороги считаются одинаковыми, если каждый сегмент первой дороги совпадает с соответствующим сегментом второй по высоте.
Входные данные
Одно число n (1 ≤ n ≤ 20).
Выходные данные
Вывести количество различных дорог длины n.