С древних времен Россия (как оказывается, не только она) известна своими плохими дорогами. Однако, начиная с послезавтрашнего дня, эта проблема будет решена! Министерство Путей Сообщения Менделеево (и не только его) разработало новую реформу, призванную значительно улучшить качество дорог. Реформа звучит следующим образом:

• Каждая строящаяся дорога состоит из n сегментов шириной 1 метр.
• Каждый сегмент имеет целую высоту от 0 до 9 метров над уровнем моря.
• Разница в высоте между двумя последовательными сегментами не должна быть больше 1 метра (то есть каждый следующий сегмент должен быть выше предыдущего на -1, 0 или 1 метр).

Миллионы отечественных автолюбителей уже ликуют, восхищенные новой реформой. Единственный вопрос, который их волнует - сколько различных дорог длины n можно построить таким образом? Дороги считаются одинаковыми, если каждый сегмент первой дороги совпадает с соответствующим сегментом второй по высоте.

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

Одно число n (1 ≤ n ≤ 20).

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

Вывести количество различных дорог длины n.