380 : 迷図と命ず

$m \times n$の迷路とは、左上の四角から反対の右下の四角へただ一つの通り道を持つ、格子の間を壁で仕切られた$m \times n$の長方形型格子である。 $9 \times 12$の迷路と$15 \times 20$の迷路の例を以下に示す。

p380_mazes.gif

異なる$m \times n$の迷路の数を$C(m,n)$で表すとしよう。回転や鏡映をさせて作られる迷路は別の迷路であると考える。

$C(1,1) = 1, C(2,2) = 4, C(3,4) = 2415, C(9,12) = 2.5720 \times 10^{46}$(有効数字5桁として四捨五入した指数表記)であることが確認できる。 $C(100,500)$を求め、5桁の有効数字として四捨五入した指数表記で表せ。

回答の際は、仮数部と指数部を分けるのに小文字の e を使うこと。例えば、答えが 1234567891011 のときは、回答のフォーマットは1.2346e12となる。