C++ :

#include<bits/stdc++.h>

#define mms(a,n) memset(a,0,sizeof((a)[0])*(n))
#define mmp(a,b,n) memcpy(a,b,sizeof((b)[0])*(n))
#define lowbit(x) ((x)&-(x))
#define pb push_back
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define lowbit(x) ((x)&-(x))
#define fo(i,l,r) for(register int i=l,_lim_=r;i<=_lim_;i++)
#define fd(i,r,l) for(register int i=r;_lim_=l;i>=_lim_;i--)

using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

namespace io{
	const int L=(1<<19)+1;
	char ibuf[L],*iS,*iT,obuf[L],*oS=obuf,*oT=obuf+L-1,c,st[55];int f,tp;
	inline char gc(){
		if(iS==iT){
			iT=(iS=ibuf)+fread(ibuf,1,L,stdin);
			return iS==iT?EOF:*iS++;
		}
		return*iS++;
	}
	inline void flush(){fwrite(obuf,1,oS-obuf,stdout);oS=obuf;}
	inline void putc(char x){*oS++=x;if(oS==oT)flush();}
	template<class I>
	inline void gi(I&x){
		for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;
		for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;
	}
	template<class I>
	inline void print(I x){
		if(!x)putc('0');if(x<0)putc('-'),x=-x;
		while(x)st[++tp]=x%10+'0',x/=10;
		while(tp)putc(st[tp--]);
	}
	inline void gs(char*s,int&l){
		for(c=gc();c!='_'&&(c<'a'||c>'z');c=gc());
		for(l=0;c=='_'||c<='z'&&c>='a';c=gc())s[l++]=c;
	}
};
using io::putc;
using io::gi;
using io::gs;
using io::print;

const int N=3e6+5,M=1e5+5,P=1004535809;
inline ll sq(ll n){ll s=sqrt(n);while(s*s<=n)s++;while(s*s>n)s--;return s;}

int pri[N],pc,mu[N],si[N],ssi[N],lst[N],sum[N],R;
bool fl[N];
inline void predo(){
	for(int x=1;x*x<R;(sum[x*x]+=x)%=P,x++)fo(y,1,sq(N-1-x*x))(sum[x*x+y*y]+=x<<1)%=P;
	fl[1]=false;
	mu[1]=si[1]=ssi[1]=lst[1]=1;
	for(int i=2;i<R;i++){
		if(!fl[i]){
			pri[++pc]=i;si[i]=i+1;lst[i]=i;mu[i]=-1;
			for(int j=i;j<=R/i;j*=i)si[j*i]=si[j]*i+1;
		}
		for(int j=1;i*pri[j]<R;j++){
			fl[i*pri[j]]=true;
			if(i%pri[j]==0){
				mu[i*pri[j]]=0;
				lst[i*pri[j]]=lst[i]*pri[j];
				si[i*pri[j]]=si[i/lst[i]]*(si[lst[i]]*pri[j]+1);
				break;
			}
			mu[i*pri[j]]=-mu[i];
			lst[i*pri[j]]=pri[j];
			si[i*pri[j]]=si[i]*(pri[j]+1);
		}
		ssi[i]=(ssi[i-1]+si[i])%P;
		(sum[i]+=sum[i-1])%=P;
	}
}

ll n,S;
struct vec{
	int f[M],g[M];
	int&operator[](ll x){return x<=S?f[x]:g[n/x];}
};

inline int s0(ll l,ll r){//\sum_{i=l}^r i
	return (l+r)%P*((r-l+1)%P)%P*(P/2+1)%P;
}
int g0(ll n){//\sum_{x^2+y^2<=n} 1
	if(n<N)return sum[n];
	static vec _g0;
	if(_g0[n])return _g0[n]; 
	int ret=0;
	for(ll x=1;x*x<=n;x++)ret=(ret+x*sq(n-x*x)*2+x)%P;
	return _g0[n]=ret;
}
int g1(ll n){//\sum_{i=1}^n \sigma(i)
	if(n<N)return ssi[n];
	static vec _g1;
	if(_g1[n])return _g1[n];
	int ret=0;
	for(ll i=1,j;i<=n;i=j+1)j=n/(n/i),ret=(ret+(ll)s0(i,j)*(n/i%P))%P;
	return _g1[n]=ret;
}
int f0(ll n){//\sum_{i=1}^n \sigma(i) g0(n/i)
	static vec _f0;
	if(_f0[n])return _f0[n];
	int ret=0;
	for(ll i=1,j;i<=n;i=j+1)j=n/(n/i),ret=(ret+(ll)(g1(j)-g1(i-1))*g0(n/i))%P;
	return _f0[n]=(ret+P)%P;
}
int f1(ll n){//\sum_{d=1}^{sq(n)} d\mu(d) f0(n/d^2)
	int ret=0;
	for(ll d=1;d*d<=n;d++)ret=(ret+(ll)mu[d]*d*f0(n/d/d))%P;
	return (ret+P)%P;
}

int main(){
	gi(n);S=sq(n);R=min(n+1,(ll)N);
	predo();
	print(f1(n));
	io::flush();
	return 0;
}