计算解锁图案

给定一个方形平铺 $n\times n$ 键锁屏和两个整数 $k_1$ 和 $k_2$，其中 $1\le k_1\le k_2\le n^2$.以下是有效模式的规则：

- 每个模式必须连接至少 $k_1$ 键和最多 $k_2$ 键。
- 所有的键必须是不同的。
- 如果连接模式中两个连续键的线穿过任何其他键，则其他键必须先前已在模式中选择。不允许跳过未选择的键。
- 使用按键的顺序很重要。

对于 $n=3$，以下是一些无效和有效的模式：



- 无效移动：4 -> 1 -> 3 -> 6
1 -> 3 线穿过模式中尚未选择的键 2。
- 无效移动：4 -> 1 -> 9 -> 2
1 -> 9 线穿过模式中尚未选择的键 5。
- 有效移动：2 -> 4 -> 1 -> 3 -> 6
1 -> 3 行有效，因为它经过已在模式中选择的键 2。
- 有效移动：6 -> 5 -> 4 -> 1 -> 9 -> 2
1 -> 9 行有效，因为它经过已在模式中选择的键 5。

定义$S(n,k_1,k_2)$为$n\times n$按键锁屏的解锁图案总数，由最少$k_1$按键和最多$k_2$按键组成。您将获得 $S(3,4,9)=389112$，这是众所周知的可能的 Android 解锁模式总数。

找到 $S(5,4,25)$。

---

感谢 百黑客 为了这个想法。