Problem Description

On an $N \times N$ lattice of points, choose $4$ points that form exactly the four vertices of a square. How many different ways are there?

Since the result may be very large, you only need to output the remainder modulo $10^9 + 7$.

As shown in the figure above, all these squares are valid.

Input Format

The input contains one integer $N$.

Output Format

Output one integer representing the answer.

4

20

Hint

For all test cases, $2 \le N \le 10^6$.

Lanqiao Cup 2019 National Contest Group C, Problem G.

Translated by ChatGPT 5