Source

This problem is adapted from Long Long OJ. All rights reserved.

Attention

The time limit for this problem is 0.1 seconds, and the memory limit is 8 MB.

Problem Description

Little A has numerous triples where the values are in the range $[1,n]$, and each triple is non-decreasing.

Little A lists all such triples without repetition or omission, and now he wants to ask you: what is the sum of all the numbers in these triples?

Please note that the output result should be taken modulo $10^9+7$.

Input Format

Input a single integer $n$.

Output Format

Output the sum of all numbers in the triples modulo $10^9+7$.

Samples

3

60

100000

493051141

Sample 1 Explanation

The valid triples are $(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)$, and the sum of all numbers in these triples is $60$.

Data Range

For $100\%$ of the data, $1\le n\le 10^9$.