# 1904 01타일

n = int(input()) # n <= 1,000,000

dp = [0] * 1000001

dp[1] = 1
dp[2] = 2 

for i in range(3,n+1):
  dp[i] = ( dp[i-2] + dp[i-1] ) % 15746

print(dp[n])

 

 

# 런타임 에러 해결 

dp = [0]*(n+1) 이런 식으로 작성하면 런타임 에러 남 

 

https://www.acmicpc.net/problem/1904

1904번: 01타일