#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,mod = 1000003;
ll sum[120];
void init(){
    sum[1] = 1;
    for(int i=2;i<=114;i++) sum[i] = sum[i-1] * 3 % mod;
}
ll query(ll x){
    if(!x) return 0;
    ll c = (ll)log2(x);
    return (sum[c + 1] + 2 * query(x - (ll)(1 << c))) % mod;
}
ll getans(ll x){
    return (((1 + n) % mod) * (n % mod) / 2 - query(n) + mod) % mod;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    init();
    cin>>n;
    cout<<getans(n)<<endl;
    return 0;
}

违规紫衫。