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

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

Мільйони вітчизняних автолюбителів уже радіють, захоплені новою реформою. Єдине питання, яке їх хвилює – скільки різних доріг довжини n можна побудувати таким чином? (дороги важаються однаковими, якщо кожен сегмент першої дороги співпадає з відповідним сегментом другої по висоті)

Вхідні дані

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

Вихідні дані

Вивести кількість різних доріг довжини \(n\).

Вхідні дані #1

1

Відповідь #1

10