#include <cstdio>
#include <vector>
using namespace std;

#define N 1000010
#define M 1000003
int p2[N],n;
int dp[N];

int gcd(int a, int b) { return b==0?a:gcd(b,a%b); }
int xgcd(int a, int b, int& x, int& y) {
  int g=a;
	x=1;y=0;
  if (b!=0) g=xgcd(b,a%b,y,x),y-=(a/b)*x;
  return g;
}
int invmod(int a, int m) {
  int x,y;
  if (xgcd(a,m,x,y)==1) return (x+m)%m;
  else return 0;
}



int calc(int x) {
  int& res=dp[x];
	if (res!=-1) return res;
  res=p2[gcd(n,x)];

  for (int y=1;y*y<=x;++y)
    if (x%y==0) {
      int y2=x/y;
      if (y<x) res=(res-calc(y)+M)%M;
      if (y2<x&&y2!=y) res=(res-calc(y2)+M)%M;
    }
  return res;
}

int main() {
  p2[0]=1;
  for (int i=1;i<N;++i) p2[i]=(p2[i-1]*2)%M;
	memset(dp,-1,sizeof(dp));

  scanf("%d",&n);
	int ans=0;
	for (int x=1;x*x<=n;++x) 
		if (n%x==0) {
			ans=(ans+(long long)(x-1)*calc(x)*invmod(x,M))%M;
			int x2=n/x;
			if (x2!=x) ans=(ans+(long long)(x2-1)*calc(x2)*invmod(x2,M))%M;
		}
	printf("%d\n",ans);
}