879 : スマホのパスワード

タッチ画面のスマホには、画面上の格子点から選択する 2 つ以上の異なる点の列で構成される「パスワード」を使用してロックを解除できるものがある。ユーザーは最初の点をタッチし、次の点まで直線状になぞり、点列が終了するまでこれを繰り返すことでパスワードを入力する。その間ユーザーの指はずっと画面と接触したままで、点から点へは直線でしか移動できない。

指が中間点を通過する直線をなぞった場合、その中間点はパスワード点列に含まれる2つの線分として扱われる。例えば、1から9の数字のラベルが付けられた$3 \times 3$格子（下に示す）で、1 - 9 と辿ると 1 - 5 - 9 と解釈される。

点を一度選択すると、その点は画面から消える。以降、その点は将来の線分の端点として使用できなくなり、そこを通過する将来の線分によって無視される。例えば、1 - 9 - 3 - 7 （これは5番の点を2度通る）はパスワード 1 - 5 - 9 - 6 - 3 - 7 を与える。

$3 \times 3$ 格子では 389488 通りのパスワードが構成できる。

$4 \times 4$ 格子で構成できるパスワードの個数を求めよ。