Description

相传高斯10岁的时候就解决了数学老师给出的难题：\(\sum_{1\le k\le 100} k\)

你的数学老师也想让你计算一个类似的问题，即：\(\sum_{1\le k\le n}k(k-1)\)

考虑到你已经高中了，难度自然要比小学生的题大。因此\(n\le 10^9\)，你只需要输出答案对1000000007取模的结果。

Input

• 一个数\(n\)

Output

• 一个数，为答案

Sample

Input

6

Output

70

Hint

• 水题