n = int(input())

p=int(1e6)+3
mod=int(1e6)

def res(v):
    return (v[0] % p, v[1] % p)

def square(v):
    a=v[0]
    b=v[1]
    return res((a**2 + 5*(b**2), 2*a*b))

def mul(v1,v2):
    a=v1[0]
    b=v1[1]
    c=v2[0]
    d=v2[1]
    return res((a*c + 5*b*d, a*d + b*c))

def pow(v, n):
    curr=v
    first=True
   
    while(n):
        if n&1!=0:
            if first:
                ret=curr
                ret=res(ret)
                first=False
            else:
                ret=mul(ret,curr)
                ret=res(ret)
        n>>=1
        curr=square(curr)
        curr=res(curr)
    return ret

def mypow2(n):
    curr=2
    ret=1
   
    while(n):
        if n&1!=0:
            ret*=curr
            ret%=p
        n>>=1
        curr*=curr
        curr%=p
    return ret


v = pow((1,+1), n)[1]
v *= 2
v %= p

v *= mypow2(n*(p-2))
v %= p

print(v%mod)


피보나치 공식에서 어차피 (1+-root5)^n의 무리수 부분의 계수 절대값이 서로 같길래

걍 그부분에 두배씌워주고, 또 2^n으로 나눠줘야하는데 너무 커서

합동식 역원으로 조져주고 했음.


근데 답이 작은 n에서는 성립하는데 큰 n에서는 안되어요.

프린이에게 도움을 주세오... ㅜㅜ