俾定一個整數 $n$。你嘅任務係計算所有三角形序列嘅數量，並輸出呢個數量除以 $10^9 + 7$ 嘅餘數。如果一個序列滿足以下條件，就稱為三角形序列：

• 序列嘅長度唔超過 $n$。
• 每個元素都係區間 $[1, n]$ 入面嘅整數。
• 呢個序列入面嘅某三個元素可以作為一個非退化三角形*嘅三條邊長。

例如當 $n = 100$ 時，三角形序列嘅例子有 $(1, 1, 1)$ 同埋 $(16, 1, 11, 25, 100)$。喺第一個序列入面，非退化三角形嘅邊長係 $(1, 1, 1)$；喺第二個序列入面，邊長係 $(16, 11, 25)$。

序列 $(16, 1, 11, 84, 100)$ 唔係三角形序列，因為冇任何三個元素可以組成非退化三角形嘅三條邊。序列 $(5, 5)$ 亦都唔係三角形序列。

* 如果一個三角形嘅面積為正數，咁佢就係非退化嘅。等價嚟講，佢嘅三個頂點唔共線。

輸入格式

唯一一行包含一個整數 $n$ ($3 \le n \le 200\,000$)。

輸出格式

輸出一個整數 —— 三角形序列嘅數量除以 $10^9 + 7$（即係 $1000000007$）嘅餘數。

範例

輸入 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)$。