問題文

$N$ 人がけの座席に、どの $2$ 人も隣り合わないように $\left\lceil\frac{N}{2}\right\rceil$ 人が座るとき、席の埋まっている状態は何通りあるでしょうか。

以下はより厳密な問題文です。$N$ 人がけの座席があり、席には $1,2,\ldots,N$ と番号がついています。$i=1,2,\ldots,N-1$ に対し、番号 $i$ の席と番号 $i+1$ の席は隣り合っています。$\left\lceil\frac{N}{2}\right\rceil$ 人が $N$ 個の席のうちのいずれかに座ります。どの $2$ 人も同じ席または隣り合った席を選ぶことはできません。このとき、席の埋まっている状態は何通りあるでしょうか。ただし $2$ つの状態が異なるとは、一方では席 $i$ に座っている人がいるがもう一方では席 $i$ に座っている人がいないような番号 $i$ が存在することをいいます。

なお、$\left\lceil\frac{N}{2}\right\rceil$ は $\frac{N}{2}$ 以上の最小の整数を表します。

入力

$N$

$N$ は $1$ 以上 $10^9$ 以下の整数です。

出力

席の埋まっている状態が何通りあるかを求めて出力してください。最後に改行してください。

サンプル

2

2

5

1