問題文

以下では、列 $X$ と整数 $s, t\ (s<t)$ について、列 $X_s, X_{s+1}, ... X_{t-1}$ (0-indexed) を $X[s, t)$ と表す。ただし、$X_{|X|+m}=X_m$ とする。
また、ある列の総和が $0$ であるとき、その列は 令和 であるとする。
また、令和である列 $X[s, t)\ (s<t)$ が only one であるとは、$s<x<t$ を満たすどの整数 $x$ についても $X[s, x)$ が令和でないことを指す。

次の条件を全て満たす整数列 $A$ の個数を $10^9+7$ で割った余りを求めなさい。
・$A$ の全ての要素は $-1$ または $1$ である。
・$A$ は令和である。
・$0≦l<|A|$ と $l<r$ を満たす整数 $l, r$ の組で $A[l, r)$ が only one なものはちょうど $K$ 個ある。

入力

$K$

・入力は全て整数である。
・$1≦K≦10^9$

出力

答えを出力し、最後に改行してください。

サンプル

4

6

3

0

100000

149033233

114514810

438430625