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