Sum of Cubes Modulo

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Use a for loop to compute (1^3+...+n^3) modulo 1000000007; do not define helper functions.

Input

One integer n in [0,100000].

Output

One integer, the sum modulo 1000000007.

Subtasks

• Subtask 1 (20%): $n\le10$.
• Subtask 2 (30%): $n\le1000$.
• Subtask 3 (50%): $n\le100000$.

Examples

Example 1

Input

3

Output

36

Explanation

1+8+27=36.

Example 2

Input

0

Output

0

Explanation

The empty sum is zero.