from sys import stdin
input=stdin.readline

mod=20210108

def main():
    N=int(input())
    if N<10**5:
        s=[1,3,10]
        for i in range(N):
            s.append((3*s[-1]+s[-2])%mod)
        print(s[N])
        return
    N-=10**5
    if N < 10**5:
        s=[3882421,10070988]
        for i in range(N):
            s.append((3*s[-1]+s[-2])%mod)
        print(s[N])
        return
    N-=10**5
    if N < 10**5:
        s=[1220246,5509401]
        for i in range(N):
            s.append((3*s[-1]+s[-2])%mod)
        print(s[N])
        return
    N-=10**5
    if N < 10**5:
        s=[10010725,15060679]
        for i in range(N):
            s.append((3*s[-1]+s[-2])%mod)
        print(s[N])
        return
    N-=10**5
    if N < 10**5:
        s=[5798169,4533124]
        for i in range(N):
            s.append((3*s[-1]+s[-2])%mod)
        print(s[N])
        return
    N-=10**5
    if N < 10**5:
        s=[19343794,15553821]
        for i in range(N):
            s.append((3*s[-1]+s[-2])%mod)
        print(s[N])
        return
    N-=10**5
    if N < 10**5:
        s=[18277469,4966775]
        for i in range(N):
            s.append((3*s[-1]+s[-2])%mod)
        print(s[N])
        return
    N-=10**5
    if N < 10**5:
        s=[16570697,706364]
        for i in range(N):
            s.append((3*s[-1]+s[-2])%mod)
        print(s[N])
        return
    N-=10**5
    if N < 10**5:
        s=[3045654,4610085]
        for i in range(N):
            s.append((3*s[-1]+s[-2])%mod)
        print(s[N])
        return
    N-=10**5
    s=[1271309,18705807]
    for i in range(N):
        s.append((3*s[-1]+s[-2])%mod)
    print(s[N])
    return

main()