# 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 を与える。

<figure><img src="https://projecteuler.net/resources/images/0879_touchscreen_159637.png?1707555645" alt=""><figcaption></figcaption></figure>

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

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

