Background

The senior high school entrance exam is here. Pg stared at the last (hardest) problem on the math paper and fell into deep thought……

Solution: https://blog.csdn.net/kkkksc03/article/details/85008125

Problem Description

As everyone knows, every lattice point (integer-coordinate point) on the plane is passed through by exactly one circle centered at the origin. We define the weight of this lattice point as the square of the radius of the circle that passes through it.

Now there is a circle centered at the origin with radius $\sqrt{R}$. You need to find the sum of the weights of all lattice points contained in this circle.

Since the answer may be very large, output it modulo $10^9+7$.

Input Format

One number $R$.

Output Format

One line with only one number.

3

12

100

16012

1234567

205275050

Hint

Explanation for Sample 1:

There are $9$ lattice points in total: $(0,0),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1)$.

Their weights are $\ 0,1,2,1,2,1,2,1,2$, and the total sum is 12.

Constraints:

For $50\%$ of the testdata, $R \le 10^{6}.$

For $100\%$ of the testdata, $R \le 10^{14}.$

Translated by ChatGPT 5