サイエンスものおきば

　以前にこのブログにて、プログラミングで解く数学の問題集のサイト「プロジェクトオイラー」をご紹介しました。（参考：「プロジェクトオイラーを遊び倒すガイド」 導入編、初級編、中級編、上級編）

　さて、今回、出された問題を解くだけでは飽き足らず、オリジナル問題を作ってみました。興味のある方はぜひチャレンジしてみて下さい。

－－－
【問】
正の整数 W, H に対し、長さ 1 のマッチ棒を 2*W*H+W+H 本ならべて、横 W × 縦 H の格子状の図形を作る。
各マッチ棒の頭の向きに応じて様々な並べ方が可能である。
W=3, H=2 の場合、並べ方は全部で 2^2*3*2+3+2 = 131072 通りある（図形全体の回転や反転は考慮しない）。このうちの 2 つを下に示す。

ここで、次の条件を満たす並べ方に着目する：すべての格子点は、少なくとも 1 個のマッチ棒の頭を含む。
左の例は、12 個の格子点の全てが少なくとも 1 個のマッチ棒の頭を含んでおり条件を満たしているが、右の例は、青丸で囲った格子点が頭を含んでおらず条件を満たしていない。

N(W, H) をこの条件を満たす並べ方の数とする。
例えば、N(1,1)=2、N(2,1)=14, N(3,2)=7618 である。
N(120,12) mod 10⁸ を求めよ。
－－－

　回答は こちら（受付終了しました）のページに行って、テキストボックスに答の８桁の数字を入力してから「回答」を押して下さい。正解なら専用の掲示板ページに飛びます。不正解なら 404 Not Found が表示されます。

　チャレンジをお待ちしています！