Use the following telephone keypad, where only the digit cells are available:
1 2 3
4 5 6
7 8 9
0Start on any digit. A knight move changes the row by two and the column by one, or the row by one and the column by two. Every landing must be on a digit. Record the starting digit and the digit reached after each move.
Return the number of distinct digit sequences of length n obtainable after exactly n - 1 moves, modulo 1000000007. Sequences may start with zero.
The keypad diagrams illustrate the two legal moves from digit 1, to 6 and 8.
Example 1:
Input: n = 3
Output: 46Explanation: Grouping the valid sequences by their final digit 0 through 9 gives counts 6, 5, 4, 5, 6, 0, 6, 5, 4, 5. Their sum is 46. Each sequence uses 2 legal knight moves.
Example 2:
Input: n = 4
Output: 104Explanation: Grouping the valid sequences by their final digit 0 through 9 gives counts 12, 10, 10, 10, 16, 0, 16, 10, 10, 10. Their sum is 104. Each sequence uses 3 legal knight moves.
Example 3:
Input: n = 5
Output: 240Explanation: Grouping the valid sequences by their final digit 0 through 9 gives counts 32, 26, 20, 26, 32, 0, 32, 26, 20, 26. Their sum is 240. Each sequence uses 4 legal knight moves.
Constraints:
1 <= n <= 5000