| 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. |