808. Knight Dialer — Count Distinct Sequences (Modulo 10^9+7)

A chess knight on a phone keypad (digits 0-9) makes n-1 moves, each an L-shaped jump. Count the number of distinct n-digit phone numbers the knight can dial, starting from ANY digit, mod 10^9+7.

Input: A positive integer n.

Output: Integer mod 10^9+7.

Examples

Input: 1
Output: 10
Explanation: 10 single-digit numbers.

Input: 2
Output: 20
Explanation: From each digit, valid knight jumps yield 20 total.

Input: 3
Output: 46
Explanation: 46 three-digit sequences.

Constraints

• 1 <= n <= 5000

Asked by