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

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

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

Вхідні дані

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

Вихідні дані

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