Black and white

縦 行、横 列のグリッドがあり、それぞれのグリッドのマスを黒色または白色に塗りつぶします。 このとき、次の条件を満たすグリッドの塗り方は何通りありますか?

• 黒色に塗られたマスは、他の黒色に塗られたマスと辺で隣接していない

ただし、答えは非常に大きくなることがあるので、答えを で割った余りを求めてください。

Note: ms以内で解きましょう

• は整数

入力は以下の形式で標準入力から与えられる。

N 

答えを一行に出力して、最後に改行せよ。

1

3

2

7

7

577

3141592

899010756