OMC211(E)

　$3×20$ のマス目を考え，上から $a_i$ 行目，左から $b_i$ 行目のマスを $X_i$ とする．このとき，$X_1,X_2,\ldots,X_{60}$ はマス目の全てのマスを通り，左上のマスから右上のマスまで，辺を共有したマスを辿る道になっているから，このような道の個数を数えれば良い．以下では，上から $c$ 行目，左から $d$ 行目のマスを $[c,d]$ で表す．
　$[1,1]$ から $0$ 回以上右に進み，初めて下に進んだマスを $[2,k]$ とすると，道はそこから $$[2,k]→ \cdots →[2,1]→[3,1]→ \cdots →[3,k]→[3,k+1]$$ と一意に定まることが分かる．特に，$3×n$ のマス目について，$[1,1]→[1,n]→[3,1]→[3,n]$ と通る道はちょうど $1$ つ存在する．従って，$3×20$ のマス目をいくつかの $3×n$ のマス目に分ける方法を考えれば，それと道が $1$ 対 $1$ 対応する．ただし，このままでは終点が $[1,20]$ ではなく $[3,20]$ ともなりうることに留意する．
　上のマス目の分け方を次のように考える．

• $3×20$ のマス目を分けている縦の線 $19$ 本のうち，$0$ 本以上を選び，それを境界とする．

　このとき，境界を $1$ 本引くと終点の右上・右下が入れ替わるため，境界はちょうど奇数本引けば良い．$19$ 本目の境界を最後に選べば，その有無で偶奇を調整できるため，特に求める答は $2^{18}=\mathbf{262144}$ である．
　以下に $3×7$ のマス目を $3$ 本の境界で分けた場合を示す：