Лингвист
Мариса, в отличие от Степана, учится на лингвистическом факультете РуНУ и, очевидно, не очень любит математику и всё, что с ней связано. Она, как и все студенты факультета, панически боится чисел, в которых модуль разности любых двух соседних цифр больше чем 1 (такие странные эти лингвисты).
Степану крайне необходимо найти все числа, которые он может использовать, чтобы не навредить психологическому состоянию Марисы. Но времени до их встречи осталось совсем мало, посчитайте хотя бы количество N-значных положительных целых чисел, которые Степан сможет использовать при встрече с Марисой.
Входные данные
В единственной строке записано число N (1 ≤ N ≤ 20).
Выходные данные
В единственной строке выведите количество N-значных положительных чисел, которые Степан смело сможет использовать при встрече с Марисой, не нанеся при этом никакого морального вреда.