Counting unlock patterns

Given a square tiled $n\times n$ key lock screen and two integers $k_1$ and $k_2$, where $1\le k_1\le k_2\le n^2$. Here are the rules for a valid pattern:

- Each pattern must connect at least $k_1$ keys and at most $k_2$ keys.
- All the keys must be distinct.
- If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key are allowed.
- The order of keys used matters.

For $n=3$, here are some invalid and valid patterns:



- Invalid move: 4 -> 1 -> 3 -> 6
Line 1 -> 3 passes through key 2 which had not been selected in the pattern.
- Invalid move: 4 -> 1 -> 9 -> 2
Line 1 -> 9 passes through key 5 which had not been selected in the pattern.
- Valid move: 2 -> 4 -> 1 -> 3 -> 6
Line 1 -> 3 is valid because it passes through key 2, which had been selected in the pattern.
- Valid move: 6 -> 5 -> 4 -> 1 -> 9 -> 2
Line 1 -> 9 is valid because it passes through key 5, which had been selected in the pattern.

Define $S(n,k_1,k_2)$ be the total number of unlock patterns of the $n\times n$ key lock screen, which consist of minimum of $k_1$ keys and maximum $k_2$ keys. You are given $S(3,4,9)=389112$, which is the well-known total number of possible Android unlock patterns.

Find $S(5,4,25)$.

---

Thanks to baihacker for the idea.