数 $n$ が与えられます。あなたの仕事は、すべての三角形列を数え上げ、その個数を $10^9 + 7$ で割った余りを出力することです。ある列が以下の条件を満たすとき、その列は三角形列と呼ばれます：

• 列の長さは $n$ を超えない。
• 各要素は区間 $[1, n]$ に含まれる整数である。
• この列のある 3 つの要素が、非退化な三角形*の 3 辺の長さになり得る。

$n = 100$ における三角形列の例として、$(1, 1, 1)$ や $(16, 1, 11, 25, 100)$ があります。1 つ目では非退化な三角形の辺は $(1, 1, 1)$ であり、2 つ目では $(16, 11, 25)$ です。

列 $(16, 1, 11, 84, 100)$ は、どの 3 つの要素も非退化な三角形の辺をなさないため、三角形列ではありません。列 $(5, 5)$ も三角形列ではありません。

* 三角形が正の面積を持つとき、非退化であるといいます。同値な言い方をすれば、その 3 頂点が同一直線上にないということです。

入力

唯一の行に整数 $n$ ($3 \le n \le 200\,000$) が含まれます。

出力

三角形列の個数を $10^9 + 7$（すなわち $1000000007$）で割った余りを表す 1 つの整数を出力してください。

入出力例

入力 1

3

出力 1

15

入力 2

4

出力 2

254

注記

$n = 3$ のとき、三角形列は $15$ 個あります：$(1,1,1), (1,2,2), (1,3,3), (2,1,2), (2,2,1), (2,2,2), (2,2,3), (2,3,2), (2,3,3), (3,1,3), (3,2,2), (3,2,3), (3,3,1), (3,3,2), (3,3,3)$。

$n = 4$ のとき、三角形列は $254$ 個あります：$(1,1,1), (1,1,1,1), (1,1,1,2), (1,1,1,3), (1,1,1,4), (1,1,2,1), \dots, (4,4,2,4), (4,4,3), (4,4,3,1), (4,4,3,2), (4,4,3,3), (4,4,3,4), (4,4,4), (4,4,4,1), (4,4,4,2), (4,4,4,3), (4,4,4,4)$。