1

2

3

4

5

6

7

8

9

10

11

12

import sys

 

dp = [0] * 1000001

n = int(sys.stdin.readline().rstrip())

 

dp[1] = 1

dp[2] = 2

 

for i in range(3, 1000001):

    dp[i] = (dp[i – 1] + dp[i – 2]) % 15746

 

print(dp[n])