経路は何通り？

ローマ水道は、縦横に流れる水が合流する地点のいくつかにおいて橋をかけ、立体交差させることで、水の流れが衝突しないように工夫されています。
下の図は、ローマ水道をシンプルにしたものです。

縦と横にn区間ずつある格子状に水道があるとして、A地点からB地点に最短距離で移動したいのですが、左下と右上を結ぶ対角線上の点のうち、スタートとゴール以外の水の流れが衝突する箇所には橋をかけ、立体交差させています。
つまり、この交差点では曲がることができません。
※図では立体交差を表現するために道を曲げていますが、立体交差の上を超えても下をくぐっても距離は変わらないものとします。

図のようにn＝4のとき、スタートからゴールまでの道順は28通りあります。
では、n＝10のときとn＝20のときについて、スタートからゴールまでの道順が何通りあるかを求めてください。

n = 10 のときは無理矢理求めた（この記事のコメントを参照）が，そのやり方は n = 20 では通用しない。

数列の法則も見いだせない（なさそうに思う）。

とっても大きな数の下 6 桁

3F1000000 （3 の フィボナッチ数列の第100万項乗）の下 6 桁を求めて下さい。念のため，

3F10 = 355 = 174449211009120179071170507 この数の下6桁は 170507

前にも，同様の質問があったけど，今回はそのときよりも大きな数になる。
しかし，ひるむ必要はない。

解答例は，この記事のコメントを参照。