　線分 $AC$ を $4$ 等分する点を，$A$ に近い方から $A_1,A_2,A_3$ とし，$A_4=C$ とする．$A$ から $A_i$ まで線の上のみを通って最短で移動する方法の総数を $f(i)$ で表す．$f(4)$ を求めればよい．\
　まず，$A_1$ を通る方法は，$A$ から $A_1$ までが $f(1)$ 通り，$A_1$ から $C$ までが $f(3)$ 通りで，これらは独立なので全体では $f(1)f(3)$ 通りである．次に，$A_1$ を通らず $A_2$ を通る方法は，同様に考えて $2f(2)$ 通りである．さらに繰り返すことで，$f(4)=f(1)f(3)+2f(2)+4f(1)+10$ が成り立つことがわかる．\
　同様に遡っていくことで，$f(3)=f(1)f(2)+2f(1)+4$，$f(2)=f(1)^2+2$ であるから，まとめると
$$ f(4) = f(1)^4 + 6f(1)^2 + 8f(1) + 14.$$
　以下，$f(1)$ を求める．線分 $AA_1$ の中点を $X$ とし，$A$ から $X$ までの最短経路が $N$ 通りあるとすると，上と同様にして $f(1)=N^2+2$ である．さらに，線分 $AX$ の中点を $Y$ とし，$A$ から $Y$ までの最短経路が $M$ 通りあるとすると，やはり $N=M^2+2$ である．$M={}\_{4}\mathrm{C}_2=6$ であるから，順に計算することで $f(4)=\mathbf{4371942276134}$ を得る．
公式解説
https://onlinemathcontest.com/contests/omc225/editorial/8064
　正方形 $ABCD$ があり，各辺を $4$ 等分するような点によって $16~(=4\times 4)$ 個の小正方形に分かれるように線を引きます．さらに，以下の操作を $3$ 回行います．ここで，各時点で「小正方形」といったとき，その内部（周上を除く）にいかなる線も引かれていないものをさすものとします．

- 線分 $AC$ が内部（周上を除く）を通るような小正方形それぞれが，各辺の中点によって$4~(=2\times 2)$ 個の小正方形に分かれるように線を引く．

最終的な状況において，線の上のみを通って$A$ から $C$ まで最短で到達する方法の総数を求めてください．

<details><summary>$1$ 回目の操作が終了した時点の図<\/summary>
![figure 1](\/images\/t7oRRV2qyJqHm61VpQxfTbXcGCNL1CxYDvdh6LkF)
<\/details>
<details><summary>$2$ 回目の操作が終了した時点の図<\/summary>
![figure 1](\/images\/bkXzFMxeqXWXQLQ3pRQ91r4XwHufYGCUjcKodXRF)
<\/details>
<details><summary>すべての操作が終了した時点の図<\/summary>
![figure 1](\/images\/WXUwZAlVVLvoFxVhLDEbfX0LQGwjNgLKqSjVeHK3)
<\/details>