#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
static const LL MODVAL = 1000000007LL;
LL ADD(LL x, LL y) { return (x+y)%MODVAL; }
LL MUL(LL x, LL y) { return (x*y)%MODVAL; }
class MegaSum { public:
int calculate(long long N)
{
LL nth = sq(N);
pair<LL,LL> p = position_of(N);
LL cnt = 0;
for(LL lane=1; lane<=nth; ++lane)
cnt = ADD(cnt, sum_in_the_lane(p, lane));
return cnt;
}
LL sq( LL N )
{
LL nth=1;
while( !(N <= nth*nth) )
++nth;
return nth;
}
pair<LL,LL> position_of( LL N )
{
// in which lane?
LL nth = sq(N);
// position
LL dif = N - (nth-1)*(nth-1);
LL y = (dif<=nth ? dif : nth);
LL x = (dif<=nth ? nth : nth+nth-dif);
if( nth%2 == 1 ) swap(x, y);
return make_pair(y,x);
}
LL sum_in_the_lane(pair<LL,LL> p, LL lane)
{
LL y = p.first;
LL x = p.second;
if( lane%2 == 0 )
{
// V
// V
//<<<<<<
LL s = lane<=x ? sumV( 1, lane, min(y,lane), lane, y, x ) : 0;
s = ADD(s, lane<=y ? sumH(lane,min(x,lane-1),lane,1,y,x) : 0);
return s;
}
else
{
// A
// A
//>>>>>>
LL s = lane<=y ? sumH( lane, 1, lane, min(x,lane), y, x ) : 0;
s = ADD(s, lane<=x ? sumV(min(y,lane-1),lane,1,lane,y,x) : 0);
return s;
}
}
LL value_of(LL y, LL x)
{
LL lane = max(x, y);
return (lane-1)*(lane-1) + (lane%2==0 ? (y<lane ? y : lane+lane-x)
: (x<lane ? x : lane+lane-y));
}
LL sumH(LL y0, LL x, LL y1, LL _, LL Y, LL X)
{
// \Sigma value_of(y0+i,x) * (X-x+1)*(Y-(y0+i)+1)
//=
// \Sigma (value_of(y0,x)+i) * (X-x+1)*(Y-(y0+i)+1)
//=
// \Sigma (V0 +i) * XX *(YY-i)
//=
// ...
assert(false);
}
LL sumV(LL y, LL x0, LL _, LL x1, LL Y, LL X)
{
assert(false);
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, MegaSum().calculate(N));}
int main(){
CASE(0)
long long N = 8LL;
int _ = 58;
END
CASE(1)
long long N = 12LL;
int _ = 282;
END
CASE(2)
long long N = 11LL;
int _ = 128;
END
CASE(3)
long long N = 6LL;
int _ = 50;
END
CASE(4)
long long N = 34539LL;
int _ = 437909839;
END
CASE(5)
long long N = 10000000000LL;
int _ = -1;
END
CASE(6)
long long N = 123456789LL;
int _ = -1;
END
}
// END CUT HERE