Sum of Weights in a Circle

It is well known that for every lattice point (x, y) in the plane, there is exactly one circle centered at the origin that passes through it. We define the weight of the lattice point as the square of the radius of that circle, i.e. for point (x,y) the weight is

[ w(x,y)=x^2+y^2, ]

Now, you are given a circle with its center at the origin and radius \( \sqrt{R} \). Your task is to compute the sum of weights of all lattice points that lie inside or on the boundary of the circle. That is, consider all integer points \((x,y)\) such that

[ x^2+y^2 \le R, ]

and compute the sum

[ S = \sum_{x^2+y^2 \le R} (x^2+y^2). ]

Since the answer might be very large, output it modulo \(10^9+7\).

inputFormat

The input consists of a single line containing one integer \(R\) (where the circle has radius \( \sqrt{R} \)).

R

outputFormat

Output a single integer, the sum of weights of all lattice points inside or on the circle, modulo \(10^9+7\).

sample

0

0