給定一個數 $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)$。