Задача №213. Ход конем
Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.
| 7 | 8 | 9 |
| 4 | 5 | 6 |
| 1 | 2 | 3 |
| 0 |
Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.
Входные данные
Вводится одно целое число N (1 ≤ N ≤ 20).
Выходные данные
Выведите искомое количество телефонных номеров.
Примеры
Входные данные
1
Выходные данные
8
Входные данные
10
Выходные данные
11728
Сдать: для сдачи задач необходимо войти в систему