I. Телефон ходом коня

Шахматная ассоциация решила выдавать сотрудникам такие телефонные номера, которые набираются на кнопочном телефоне ходом коня. Клавиатура выглядит так:

7 8 9
4 5 6
1 2 3
  0

Каждая следующая цифра набирается ходом шахматного коня от предыдущей. Номер не может начинаться ни с цифры $0$, ни с цифры $8$.

Сколько существует таких номеров длины $N$?

Одна строка содержит число $N$ ($1 \le N \le 20$).

Одно число — количество телефонных номеров.