Задача D. Трискайдекафобия ≡

Условие

Трискайдекафобия — болезненная боязнь числа 13. Наличие фобии заставляет человека испытывать повышенную тревожность при контакте с любым объектом, в описании или названии которого есть 13. Это влияет на поведение, решения и общее состояние человека с данным расстройством. В результате в некоторых зданиях этажи нумеруются так, чтобы не нервировать трискаидекафобов: после 12-го этажа может сразу следовать 14-й. Иногда это также относится к номерам домов и помещений. В современной "Формуле-1" нет болида под номером 13.

Трискаидекафоб страдает от навязчивых мыслей, пессимистичен относительно ближайшего будущего после контакта с числом 13. Из-за данной фобии развивается обсессивно-компульсивное расстройство и провоцирует ухудшение состояния. Для предотвращения развития трискаидекафобии необходимо разобраться в причинах и устранить проблему как можно раньше.

Трискайдекафобией страдал австрийский композитор Арнольд Шёнберг. Он родился 13-го числа, что он всю жизнь считал дурным предзнаменованием. Однажды он наотрез отказался взять в аренду дом под номером 13. Композитор боялся того дня, когда ему исполнится 76, потому что в сумме эти цифры составляют пресловутое число 13. Более того, эта дата пришлась на пятницу 13 июля 1951 года. По слухам, тогда он весь день пролежал в постели, готовясь к предполагаемой смерти. Жена пыталась уговорить мужа встать и "прекратить эти глупости", и каково же было её потрясение, когда тот лишь вымолвил слово "гармония" и умер за 13 минут до полуночи.

Арнольд считает число хорошим, если в нём нет ни одной подстроки "13". Сколько хороших чисел среди всех n-значных?

Формат входных данных

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 18

Пояснение к примеру

В первом примере нужно найти хорошие числа среди всех двузначных. В диапазоне от 10 до 99 есть только одно нехорошее число 13.

Примеры тестов

2

89

4

8721