#include<bits/stdc++.h>
#pragma G++ optimize(2)
using namespace std;
typedef long long ll;
const int N=1000003;
inline ll read()
{
    ll x=0;
    int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(ll x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
ll e_gcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1;y=0;
		return a;
	}
	ll gcd=e_gcd(b,a%b,y,x);
	y-=a/b*x;
	return gcd;
}
ll n,x,y;
int main(){
	n=read();
	write((e_gcd(n,N,x,y))%N);
	return 0;
}