n = int(input())
arr = [1, 1]
for i in range(2, n+1):
    arr[i%2] = sum(arr) % 15746
print(arr[n%2])

# 2 1*2 + 1
# 1*2 +1
# 1 1 1
# 2 2 11 00
# 3 3 111 100 001
# 4 5 1111 1100 0011 1001 0000
# 5 8 11111 11100 11001 10011 00111 10000 00100 00001
# 6 13 111111 111100 111001 110011 100111 001111 000011 001100 110000 000000 100001 001001 100100
