問題文

以下では、列 $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\leqq l<|A|$ と $l<r$ を満たす整数 $l,r$ の組で $A[l,r)$ が only one なものはちょうど $K$ 個ある。

入力

$K$

・入力は全て整数である。
・$1\leqq K\leqq {10}^9$

出力

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

サンプル

4

6

3

0

100000

149033233

114514810

438430625