1839: MegaSum(Harder Edition)

Let us define an infinite table of integers as follows: Each cell is uniquely identified by the value it contains. Let us define S(X) as the sum of all the values in the rectangle with cell 1 as its upper-left corner and cell X as its lower-right corner. For example, S(12) is the sum of all the values in the green rectangle shown above. You are given a long N. First, find the rectangle with cell 1 as its upper-left corner and cell N as its lower-right corner. Then, calculate the sum of S(X) for all values X inside this rectangle. Return this sum modulo 1,000,000,007. For example, if N is 8, you would first find the 3 x 2 rectangle with 1 in its upper-left corner and 8 in its lower-right corner. You would then calculate S(X) for each value X in this rectangle: S(1) = 1, S(2) = 3, S(9) = 12, S(4) = 5, S(3) = 10, and S(8) = 27. You would them sum these values to get 1 + 3 + 12 + 5 + 10 + 27 = 58.

The input is a sequence of datasets. A dataset is a line containing one integer n ( 1<=n<=10000000000).

The output should be composed of lines, each corresponding to an input dataset. . Since the number can be extremely big, you are only required to output the answer mod 1,000,000,007. No extra characters (e.g. extra spaces) should appear in the output.

8
12
11
6
34539
72092288
382105
4863616
10000000000

58
282
128
50
437909839
999999996
79
32
832250385