Problem 879

Touch-screen Password

A touch-screen device can be unlocked with a “password” consisting of a sequence of two or more distinct spots that the user selects from a rectangular grid of spots on the screen. The user enters their sequence by touching the first spot, then tracing a straight line segment to the next spot, and so on until the end of the sequence. The user’s finger remains in contact with the screen throughout, and may only move in straight line segments from spot to spot.

If the finger traces a straight line that passes over an intermediate spot, then that is treated as two line segments with the intermediate spot included in the password sequence. For example, on a $3\times 3$ grid labelled with digits $1$ to $9$ (shown below), tracing $1-9$ is interpreted as $1-5-9$.

Once a spot has been selected it disappears from the screen. Thereafter, the spot may not be used as an endpoint of future line segments, and it is ignored by any future line segments which happen to pass through it. For example, tracing $1-9-3-7$ (which crosses the $5$ spot twice) will give the password $1-5-9-6-3-7$.

There are $389488$ different passwords that can be formed on a $3 \times 3$ grid.

Find the number of different passwords that can be formed on a $4 \times 4$ grid.

触屏密码

触屏设备的解锁“密码”是由用户从屏幕上的长方形点阵中选择两个至多个不同触点组成的序列。用户先触摸第一个触点，然后沿直线移动到第二个触点，依此类推直至完成序列。在这过程中，用户的手指必须始终接触屏幕，且只能沿直线移动。

如果在手指沿直线移动时经过了一个中间触点，则应当将该中间触点加入序列并视为两段移动。例如，考虑一个大小为$3 \times 3$且标有数字$1$至$9$的点阵（如下所示），序列$1-9$实际上应当视为序列$1-5-9$。

触点被接触后就会从屏幕上消失，在此之后，既不能作为未来移动时的终点，也不会因为在移动时经过而被作为中间触点再次加入序列。例如，序列$1-9-3-7$（期间会经过触点$5$两次）实际上应当视为序列$1-5-9-6-3-7$。

在$3\times 3$的点阵上，一共有$389488$种不同的密码。

求在$4\times 4$的点阵上，一共有多少种不同的密码？