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