版权声明

本题版权归 Long Long OJ 所有。

注意

本题的时间限制为 0.1 秒，空间限制为 8 MB。

题目描述

小 A 有很多个三元组，其中值域为 $[1,n]$，并且每个三元组都是单调不降的。

小 A 把所有满足条件的三元组不重不漏地列出来，现在他想考考你，这些三元组的数字之和是多少？

请注意，输出的结果对 $10^9+7$ 取摸。

输入格式

输入一个数 $n$。

输出格式

输出这些数的和对 $10^9+7$ 取摸的结果。

样例

3

60

100000

493051141

提示

样例 $1$ 解释：

满足条件的三元组有 $(1,1,1),(1,1,2),(1,1,3),(1,2,2),(1,2,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3)$，这些数的和为 $60$。

对于 $100\%$ 的数据，$1\le n\le 10^9$。