Count Digit Strings Produced by Knight Moves on a Phone Pad

### Problem The numeric keypad has rows `1 2 3`, `4 5 6`, `7 8 9`, and a final row with0 in its middle column; the other two final-row positions are unusable. Place a chess knight on any digit, then make n-1 valid moves, each changing row/column by(2,1) or(1,2). Record every visited digit, including the start. Return the number of distinct length-n digit strings modulo `10^9+7`. Leading0 is allowed. ```cpp class Solution { public: int knightDialer(int n); }; ``` ### Examples **Example 1:** ```text Input: n = 3 Output: 46 Explanation: Counting paths by their middle digit gives seven degree-two digits contributing4 each and two degree-three digits contributing9 each:28+18=46; digit5 contributes0. ``` **Example 2:** ```text Input: n = 4 Output: 104 Explanation: Length-three path counts ending at digits0 through9 are[6,5,4,5,6,0,6,5,4,5]. Multiplying each by its outgoing degree and summing gives104. ``` ### Constraints - `1 <= n <= 5000`. ### Contract considerations The textual keypad reproduces the original diagram. Numeric output is a modular count, not a probability or an arbitrary valid path. ```hint Read the boundary condition Count strings by the digit where the knight finishes, and extend those counts through legal edges. ``` ### Boundary reminders The textual keypad reproduces the original diagram. Numeric output is a modular count, not a probability or an arbitrary valid path.