#include<cstdio>

#include<iostream>

#define mo 1000003

using namespace std;

long long n,d,z,ans,a[],b[],v,p;

int i,t;

int main(){

    cin>>v;

    n=v;z=;d=z<<;

    t=;

    while(n!=){

        if(n>=d){

            n=n-d;

            a[++a[]]=t;

        }

        d>>=;

        t--;

    }

    b[]=;

    for(int i=;i<=a[];i++)b[i]=(b[i-]*)%mo;

    for(int i=;i<=a[];i++)ans+=b[a[i]]*(long long)(z<<i-);

    p=(((z+v%mo)*(v%mo))/);

    p%=mo;

    ans%=mo;

    if(p<ans)p+=mo;

    p=(p-ans)%mo;

    cout<<p;

    return ;

}