Knight hops on a phone keypad

Put a chess knight on the keys of a phone:

1 2 3
4 5 6
7 8 9
  0

A knight hop goes two keys in one straight direction and one key sideways (an L). A hop is only allowed if it lands on a key; there are no keys to the left or right of 0. For example, from 4 the knight can reach 3, 9 and 0, and from 5 it can't move at all.

Starting on key start, the knight dials a number by making hops: the starting key is the first digit and every key it lands on adds a digit. Keys may be revisited.

Write

def count_dialed(start: str, length: int, end: str | None = None) -> int

that returns how many different numbers of exactly length digits the knight can dial from start. If end is given, count only numbers whose last digit is end. The count can be huge; return it modulo 1_000_000_007.

• start and end are single digits "0"–"9". length >= 1.
• A 1-digit number is just start, so length == 1 gives 1 (or 0 if end is given and differs from start).

count_dialed("1", 1)        # 1   ("1")
count_dialed("1", 2)        # 2   ("16", "18")
count_dialed("1", 3)        # 5   ("160", "161", "167", "181", "183")
count_dialed("1", 3, "1")   # 2   ("161", "181")
count_dialed("5", 4)        # 0

length can be up to 50,000. Walking every path grows exponentially (about 2 branches per hop), and recursion 50,000 calls deep, even memoised, overflows Python's stack.