Module: One-dimensional dynamics


Problem

6 /7


Knight's move

Problem

The Chess Association decided to equip all its employees with such telephone numbers that would be dialed on a push-button telephone with a knight's move. For example, the knight's move calls 340-4927. At the same time, the phone number cannot begin with either the number 0 or the number 8.
 
The phone keyboard looks like this:
7 8 9
4 5 6
1 2 3
  0  
 
Write a program to determine the number of telephone numbers of length N dialed by the knight.
 
Input: Input is an integer N (\(1< =N<=50\)).
 
Output: output the number of phone numbers you are looking for.
 

Examples
# Input Output
1 2 16