#include<cstdio>
#include<cstring>
const int mod=1e6+3;
struct mat{
    int c[30][30];
    void clear(){memset(c,0,sizeof(c));}
    mat operator *(const mat &o)const{
        mat r;
        r.clear();
        for(int i=1;i<=29;i++)
        for(int k=1;k<=29;k++)
        for(int j=1;j<=29;j++)
        if(c[i][k]&&o.c[k][j])
        r.c[i][j]=(r.c[i][j]+1ll*c[i][k]*o.c[k][j])%mod;
        return r;
    }
}f,g;
int ksm(int u,int v){
	int res=1;
	for(;v;v>>=1,u=1ll*u*u%mod)
	if(v&1)res=1ll*res*u%mod;
	return res;
}
typedef long long LL;
LL n;
int main(){
	scanf("%lld",&n);
	f.c[1][9]=1;//f[0]=1
	for(int i=1;i<=8;i++)g.c[i+1][i]=1;
	for(int i=1;i<=9;i++)g.c[i][9]=1;
	for(int i=10;i<=17;i++)g.c[i+1][i]=1;
	for(int i=1;i<=9;i++)g.c[i][18]=10-i;
	for(int i=10;i<=18;i++)g.c[i][18]=10;
	for(int i=19;i<=26;i++)g.c[i+1][i]=1;
	for(int i=1;i<=9;i++)g.c[i][27]=(10-i)*(10-i);
	for(int i=10;i<=18;i++)g.c[i][27]=(19-i)*20;
	for(int i=19;i<=27;i++)g.c[i][27]=100;
	g.c[18][28]=g.c[28][28]=1;
	g.c[27][29]=g.c[29][29]=1;
    //我这里求的是n-1的\sum，所以n要加1
	for(++n;n;n>>=1,g=g*g)
	if(n&1)f=f*g;
	printf("%lld\n",1ll*(1ll*f.c[1][28]*f.c[1][28]-f.c[1][29]+mod)%mod*ksm(2,mod-2)%mod);
}