2025.09.07

'''
def f(num) :
    global a
    for i in range(len(a)) :
        if a[i][0]==num:
            return i
    return -1


n=int(input())
a=[]
for i in range(n):
    c,no,name=input().split()
    x=f(int(no))
    if c=='I':
        if x==-1:
            a.append([int(no),name])
        # else:
        #     print('I-deleted')
    elif c=='D':
        # print('deleted-')
        if x!=-1:
            # print('deleted')
            del a[x]
a.sort(key=lambda x:x[0])
d=list(map(int,input().split()))
for i in range(5):
    print(a[d[i]-1][0],a[d[i]-1][1],sep=' ')


# a = [[1,2,3],[1,1,1]]
# a.count(1) -> 0
'''

# import sys
# sys.setrecursionlimit(100000000)
#
# def f(x) :
#     if x==0 :
#         return
#     print(x)
#     f(x-1)
#
# n = int(input())
# f(n)
'''
import sys
sys.setrecursionlimit(10000)


def f(x):
    global a
    if x==1:
        return 1
    elif x==2:
        return 1
    if a[x-1]==0:
        a[x-1]=f(x-1)
    if a[x-2]==0:
        a[x-2]=f(x-2)
    return a[x-1]+a[x-2]


a=[0]*201
n=int(input())
print(f(n)%10009)
import sys
sys.setrecursionlimit(2147483647)


def f(x,y):
    if x==0:
        return
    f(x//y,y)
    if x%y<=9:
        print(x%y,end='')
    else:
        print(chr(x%y+55),end='')
    return


n,k=map(int,input().split())
f(n,k)

'''
import sys
sys.setrecursionlimit(2147483647)
a=[]
b=[]


def f(x,k):
    if x==0:
        return
    if k==0:
        f(x//2,0)
        a.append(x%2)
    else:
        f(x//2,1)
        b.append(x%2)
    return


c,d=map(int,input().split())
f(c,0)
f(d,1)
for i in range(31):
    if a[i]!=b[i]:
        e=i
        break