Problem Background

Pg is staring at the final question on the math exam, lost in thought...

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

Problem Description

As we all know, every integer point in the plane is uniquely intersected by a circle with its center at the origin. We define the weight of this integer point as the square of the radius of the intersecting circle.

Given a circle with its center at the origin and a radius of $\sqrt{R}$, you are required to find the sum of the weights of all integer points contained within this circle.

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

Input Format

A single number $R$.

Output Format

A single line containing one number.

Sample Input and Output

Sample Input #1

3

Sample Output #1

12

Sample Input #2

100

Sample Output #2

16012

Sample Input #3

1234567

Sample Output #3

205275050

Notes

Explanation for Sample 1:

It contains $9$ integer points: $(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$ respectively, summing up to 12.

For 50% of the data, $R \le 10^6$.

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

见题面 Input 部分

见题面 Output 部分