n = int(input('Which Fibonacci number? ' )) # Taking Input
stack = []
while(n>0):
stack.append(n%2) #Storing binary rep of n
n = n//2
a = 0
b = 1
while (len(stack) != 0):
c = ((2*b - a)*a)%10**100
d = (a*a + b*b)%10**100
if(stack.pop()%2==0):
a = c
b =d
else:
a = d
b = (c+d)%10**100
print(a)
