Count Squares in a Grid

Given an N × N grid of points, your task is to count the number of ways to choose 4 distinct points that form the vertices of a square. A square is considered valid regardless of its orientation (it may be rotated) as long as its 4 vertices are grid points.

In mathematical terms, you need to count the number of squares whose vertices are among the grid points. It can be shown that the total number of squares is given by the formula $$ \frac{N^2\,(N^2-1)}{12}, $$ where the division is exact. Since the answer can be very large, output the result modulo \(10^9+7\).

Note: When \(N = 1\) there are no squares.

inputFormat

The input consists of a single integer \(N\) representing the number of points in each row (and column) of the grid. You may assume \(1 \leq N \leq 10^9\).

outputFormat

Output a single integer: the number of squares that can be formed, taken modulo \(10^9+7\).

sample

2

1