给定一个整数 $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)$。