1359: Хід конем


Відправити розв'язок


Бали:6
Time limit:1.0s
Memory limit:63M
Author:

Problem type

Шахова асоціація вирішила оснастити всіх своїх співробітників такими телефонними номерами, які б набиралися на кнопковому телефоні ходом коня. Наприклад, ходом коня набирається телефон 340-4927. При цьому телефонний номер не може починатися ні з цифри 0, ні з цифри 8.

Клавіатура телефону виглядає так:

7 8 9
4 5 6
1 2 3
  0

Напишіть програму, що визначає кількість телефонних номерів довжини N, набираються ходом коня.

Формат вхідних даних

У стандартному потоці міститься ціле число N (1 ≤ N ≤ 100).

Формат вихідних даних

У стандартний потік вивести шукану кількість телефонних номерів.

Приклад вхідних даних

2

Приклад вихідних даних

16

Коментарі


  • -1
    zvit
     прокоментував о Березень 22, 2018

    У тестах N<=50 - це зроблено для того, щоб обійтися без довгої арифметики