Counting Ordered Quadruples of Squares

Given a positive integer (n), count the number of ordered quadruples of integers ((a, b, c, d)) satisfying the equation [ a^2 + b^2 + c^2 + d^2 = n, ] and output the answer modulo (10^9+7).

Note: Each of (a, b, c, d) can be any integer such that their square does not exceed (n).

inputFormat

A single line containing the positive integer (n).

outputFormat

Output a single integer that is the number of ordered quadruples ((a, b, c, d)) satisfying (a^2 + b^2 + c^2 + d^2 = n) modulo (10^9+7).

sample

1

8