The chess knight has a unique movement style, jumping two cells vertically and one cell horizontally, or two cells horizontally and one cell vertically.
A standard telephone keypad is arranged as follows:
The keys 1, 2, 3 form the first row; 4, 5, 6 form the second row; 7, 8, 9 form the third row; and *, 0, # form the fourth row.
A knight can only stand on a numeric key (0 to 9); the * and # keys cannot be used.
Given an integer n, return the number of distinct phone numbers of length n that can be dialed.
The knight may start on any numeric key, and then it must make n - 1 valid knight jumps to dial a number of length n.
Since the answer can be very large, return it modulo
Constraints:
n
The chess knight has a unique movement style, jumping two cells vertically and one cell horizontally, or two cells horizontally and one cell vertically.
A standard telephone keypad is arranged as follows:
The keys 1, 2, 3 form the first row; 4, 5, 6 form the second row; 7, 8, 9 form the third row; and *, 0, # form the fourth row.
A knight can only stand on a numeric key (0 to 9); the * and # keys cannot be used.
Given an integer n, return the number of distinct phone numbers of length n that can be dialed.
The knight may start on any numeric key, and then it must make n - 1 valid knight jumps to dial a number of length n.
Since the answer can be very large, return it modulo
Constraints:
n