#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,tune=native")
using namespace std;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
int rint();
char rch();
long long rlong();
template <int MOD>
struct ModInt {
  static const int Mod = MOD;
  unsigned x;
  ModInt() : x(0) {}
  ModInt(signed sig) {
    int sigt = sig % MOD;
    if (sigt < 0) sigt += MOD;
    x = sigt;
  }
  ModInt(signed long long sig) {
    int sigt = sig % MOD;
    if (sigt < 0) sigt += MOD;
    x = sigt;
  }
  int get() const { return (int)x; }
  ModInt &operator+=(ModInt that) {
    if ((x += that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator-=(ModInt that) {
    if ((x += MOD - that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator*=(ModInt that) {
    x = (unsigned long long)x * that.x % MOD;
    return *this;
  }
  ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
  ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
  ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
  ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
  ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
  ModInt inverse() const {
    signed a = x, b = MOD, u = 1, v = 0;
    while (b) {
      signed t = a / b;
      a -= t * b;
      std::swap(a, b);
      u -= t * v;
      std::swap(u, v);
    }
    if (u < 0) u += Mod;
    ModInt res;
    res.x = (unsigned)u;
    return res;
  }
  bool operator==(ModInt that) const { return x == that.x; }
  bool operator!=(ModInt that) const { return x != that.x; }
  ModInt operator-() const {
    ModInt t;
    t.x = x == 0 ? 0 : Mod - x;
    return t;
  }
};
template <int MOD>
ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
  ModInt<MOD> r = 1;
  while (k) {
    if (k & 1) r *= a;
    a *= a;
    k >>= 1;
  }
  return r;
}
long long gn;
long long floorn[4];
ModInt<1000000007> query(long long inl, long long r, int deg) {
  ModInt<1000000007> q = (r - inl) / 4;
  ModInt<1000000007> l = inl;
  if (deg == 0) {
    return q + 1;
  } else if (deg == 1) {
    return (q + 1) * (l + ModInt<1000000007>(2) * q);
  } else if (deg == 2) {
    return ((q + 1) *
            (ModInt<1000000007>(3) * l * l + ModInt<1000000007>(12) * l * q +
             ModInt<1000000007>(8) * q * (ModInt<1000000007>(2) * q + 1))) /
           3;
  } else {
    return (q + 1) * (l + ModInt<1000000007>(2) * q) *
           (l * l + ModInt<1000000007>(4) * l * q +
            ModInt<1000000007>(8) * q * (q + 1));
  }
}
ModInt<1000000007> divisorContribution(int d, int otherMod4, int deg) {
  long long n = gn;
  long long lo = d + 1, hi = n / d;
  while (lo % 4 != otherMod4) ++lo;
  while (hi >= 0 && hi % 4 != otherMod4) --hi;
  if (lo > hi) return 0;
  ModInt<1000000007> dpow = 1;
  for (int i = 0; i < deg; i++) dpow *= d;
  return query(lo, hi, deg) * dpow;
}
ModInt<1000000007> degcoeff[4];
ModInt<1000000007> solve() {
  int slim = sqrt((long double)gn) + 3;
  ModInt<1000000007> sumans = 0;
  for (int deg = 0; deg <= 3; deg++) {
    ModInt<1000000007> degans = 0;
    for (int d = 1; d <= slim; d++) {
      ModInt<1000000007> contrib1 = divisorContribution(d, 1, deg);
      ModInt<1000000007> contrib3 = divisorContribution(d, 3, deg);
      if (d % 4 == 1 || d % 4 == 3) {
        ModInt<1000000007> all = contrib1 + contrib3 +
                                 divisorContribution(d, 0, deg) +
                                 divisorContribution(d, 2, deg);
        if (d % 4 == 1)
          contrib1 += all;
        else if (d % 4 == 3)
          contrib3 += all;
      }
      long long d2 = d * (long long)d;
      if (d2 <= gn) {
        ModInt<1000000007> d2pow = 1;
        for (int i = 0; i < deg; i++) d2pow *= ModInt<1000000007>(d2);
        if (d % 4 == 1)
          contrib1 += d2pow;
        else if (d % 4 == 3)
          contrib3 += d2pow;
      }
      ModInt<1000000007> contrib =
          ModInt<1000000007>(4) * (contrib1 - contrib3);
      degans += contrib;
    }
    sumans += degans * degcoeff[deg];
  }
  return sumans;
}
void initcoeff() {
  ModInt<1000000007> m = gn;
  degcoeff[0] = (m * m * m) / 6 + (m * m) / 2 + m / 3;
  degcoeff[1] = m / 2 + ModInt<1000000007>(2) / 3;
  degcoeff[2] = -m / 2 - 1;
  degcoeff[3] = ModInt<1000000007>(1) / 3;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> gn;
  initcoeff();
  ModInt<1000000007> final = solve();
  final += degcoeff[0];
  printf("%d\n", final.get());
}

### Prompt

Please create a solution in CPP to the following problem:

Everything red frightens Nian the monster. So do red paper and... you, red on Codeforces, potential or real.

Big Banban has got a piece of paper with endless lattice points, where lattice points form squares with the same area. His most favorite closed shape is the circle because of its beauty and simplicity. Once he had obtained this piece of paper, he prepares it for paper-cutting.

<image>

He drew n concentric circles on it and numbered these circles from 1 to n such that the center of each circle is the same lattice point and the radius of the k-th circle is <image> times the length of a lattice edge.

Define the degree of beauty of a lattice point as the summation of the indices of circles such that this lattice point is inside them, or on their bounds. Banban wanted to ask you the total degree of beauty of all the lattice points, but changed his mind.

Defining the total degree of beauty of all the lattice points on a piece of paper with n circles as f(n), you are asked to figure out <image>.

Input

The first line contains one integer m (1 ≤ m ≤ 1012).

Output

In the first line print one integer representing <image>.

Examples

Input

5


Output

387


Input

233


Output

788243189

Note

A piece of paper with 5 circles is shown in the following.

<image>

There are 5 types of lattice points where the degree of beauty of each red point is 1 + 2 + 3 + 4 + 5 = 15, the degree of beauty of each orange point is 2 + 3 + 4 + 5 = 14, the degree of beauty of each green point is 4 + 5 = 9, the degree of beauty of each blue point is 5 and the degree of beauty of each gray point is 0. Therefore, f(5) = 5·15 + 4·14 + 4·9 + 8·5 = 207.

Similarly, f(1) = 5, f(2) = 23, f(3) = 50, f(4) = 102 and consequently <image>.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,tune=native")
using namespace std;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
int rint();
char rch();
long long rlong();
template <int MOD>
struct ModInt {
  static const int Mod = MOD;
  unsigned x;
  ModInt() : x(0) {}
  ModInt(signed sig) {
    int sigt = sig % MOD;
    if (sigt < 0) sigt += MOD;
    x = sigt;
  }
  ModInt(signed long long sig) {
    int sigt = sig % MOD;
    if (sigt < 0) sigt += MOD;
    x = sigt;
  }
  int get() const { return (int)x; }
  ModInt &operator+=(ModInt that) {
    if ((x += that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator-=(ModInt that) {
    if ((x += MOD - that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator*=(ModInt that) {
    x = (unsigned long long)x * that.x % MOD;
    return *this;
  }
  ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
  ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
  ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
  ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
  ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
  ModInt inverse() const {
    signed a = x, b = MOD, u = 1, v = 0;
    while (b) {
      signed t = a / b;
      a -= t * b;
      std::swap(a, b);
      u -= t * v;
      std::swap(u, v);
    }
    if (u < 0) u += Mod;
    ModInt res;
    res.x = (unsigned)u;
    return res;
  }
  bool operator==(ModInt that) const { return x == that.x; }
  bool operator!=(ModInt that) const { return x != that.x; }
  ModInt operator-() const {
    ModInt t;
    t.x = x == 0 ? 0 : Mod - x;
    return t;
  }
};
template <int MOD>
ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
  ModInt<MOD> r = 1;
  while (k) {
    if (k & 1) r *= a;
    a *= a;
    k >>= 1;
  }
  return r;
}
long long gn;
long long floorn[4];
ModInt<1000000007> query(long long inl, long long r, int deg) {
  ModInt<1000000007> q = (r - inl) / 4;
  ModInt<1000000007> l = inl;
  if (deg == 0) {
    return q + 1;
  } else if (deg == 1) {
    return (q + 1) * (l + ModInt<1000000007>(2) * q);
  } else if (deg == 2) {
    return ((q + 1) *
            (ModInt<1000000007>(3) * l * l + ModInt<1000000007>(12) * l * q +
             ModInt<1000000007>(8) * q * (ModInt<1000000007>(2) * q + 1))) /
           3;
  } else {
    return (q + 1) * (l + ModInt<1000000007>(2) * q) *
           (l * l + ModInt<1000000007>(4) * l * q +
            ModInt<1000000007>(8) * q * (q + 1));
  }
}
ModInt<1000000007> divisorContribution(int d, int otherMod4, int deg) {
  long long n = gn;
  long long lo = d + 1, hi = n / d;
  while (lo % 4 != otherMod4) ++lo;
  while (hi >= 0 && hi % 4 != otherMod4) --hi;
  if (lo > hi) return 0;
  ModInt<1000000007> dpow = 1;
  for (int i = 0; i < deg; i++) dpow *= d;
  return query(lo, hi, deg) * dpow;
}
ModInt<1000000007> degcoeff[4];
ModInt<1000000007> solve() {
  int slim = sqrt((long double)gn) + 3;
  ModInt<1000000007> sumans = 0;
  for (int deg = 0; deg <= 3; deg++) {
    ModInt<1000000007> degans = 0;
    for (int d = 1; d <= slim; d++) {
      ModInt<1000000007> contrib1 = divisorContribution(d, 1, deg);
      ModInt<1000000007> contrib3 = divisorContribution(d, 3, deg);
      if (d % 4 == 1 || d % 4 == 3) {
        ModInt<1000000007> all = contrib1 + contrib3 +
                                 divisorContribution(d, 0, deg) +
                                 divisorContribution(d, 2, deg);
        if (d % 4 == 1)
          contrib1 += all;
        else if (d % 4 == 3)
          contrib3 += all;
      }
      long long d2 = d * (long long)d;
      if (d2 <= gn) {
        ModInt<1000000007> d2pow = 1;
        for (int i = 0; i < deg; i++) d2pow *= ModInt<1000000007>(d2);
        if (d % 4 == 1)
          contrib1 += d2pow;
        else if (d % 4 == 3)
          contrib3 += d2pow;
      }
      ModInt<1000000007> contrib =
          ModInt<1000000007>(4) * (contrib1 - contrib3);
      degans += contrib;
    }
    sumans += degans * degcoeff[deg];
  }
  return sumans;
}
void initcoeff() {
  ModInt<1000000007> m = gn;
  degcoeff[0] = (m * m * m) / 6 + (m * m) / 2 + m / 3;
  degcoeff[1] = m / 2 + ModInt<1000000007>(2) / 3;
  degcoeff[2] = -m / 2 - 1;
  degcoeff[3] = ModInt<1000000007>(1) / 3;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> gn;
  initcoeff();
  ModInt<1000000007> final = solve();
  final += degcoeff[0];
  printf("%d\n", final.get());
}

```