#include <iostream> #include <vector> #include <cstdio> #include <sstream> #include <map> #include <string> #include <algorithm> #include <queue> #include <cmath> #include <set> using namespace std; #define MOD 1000003 long long gcd(long long a, long long b){ if(b==0) return a; return gcd(b, a%b); } long long lcm(long long a, long long b){ if(a<b) swap(a,b); if(b==1) return a; return a * (b/gcd(a,b)); } int main(){ long long L; cin >> L; int ans = 0; for(long long n=1; n<(L>>1LL); ++n){ for(long long m=n+1; 8*m*(m+n)<=L; m+=2){ if(gcd(n,m) == 1){ ans++; } } } ans %= MOD; cout << ans << endl; return 0; }