To help Lavanya learn all about binary numbers and binary sequences, her father has bought her a collection of square tiles, each of which has either a 0 or a 1 written on it. Her brother Nikhil has played a rather nasty prank. He has glued together pairs of tiles with 0 written on them. Lavanya now has square tiles with 1 on them and rectangular tiles with two 0's on them, made up of two square tiles with 0 stuck together). Thus, she can no longer make all possible binary sequences using these tiles.
To amuse herself, Lavanya has decided to pick a number $N$ and try and construct as many binary sequences of length $N$ as possible using her collection of tiles. For example if $N$ = 1, she can only make the sequence 1. For $N$=2, she can make 11 and 00. For $N$=4, there are 5 possibilities: 0011, 0000, 1001, 1100 and 1111.
Lavanya would like you to write a program to compute the number of arrangements possible with $N$ tiles so that she can verify that she has generated all of them. Since she cannot count beyond 15746, it is sufficient to report this number modulo 15746.

-----Input:-----
A single line with a single integer $N$.

-----Output:-----
A single integer indicating the number of binary sequences of length $N$, modulo 15746, that Lavanya can make using her tiles.

-----Constraints:-----
You may assume that $N \leq$ 1000000.

-----Sample Input:-----
4

-----Sample Output:-----
5

-----Explanation:-----
This corresponds to the example discussed above.

Difficulty: interview

Starter code:

Solutions:
n=int(input())
modulo=15746
num=[1,1]
for i in range(2,n+1):
    num.append((num[i-1]+num[i-2])%modulo)
print(num[n])

def EXEC(n):
    if n < 3: return n
    else:
        x, y = 1, 2
        for _ in range(2, n):
            z = (x + y) % 15746
            x, y = y, z
        return y % 15746


print(EXEC(int(input())))

def fib(n):
    s1,s2=1,2
    if n==1:
        return s1
    elif n==2:
        return s2
    else:
        for i in range(2,n):
            s3=(s1+s2)%15746
            s1=s2
            s2=s3
        return s2%15746

try:
    n=int(input())
    z=fib(n)
    print(z)
  
except:
  pass


# // Problem : Zero One Tiles
# // Contest : CodeChef - IARCS OPC Judge Problems
# // URL : https://www.codechef.com/IARCSJUD/problems/TILES01
# // Memory Limit : 256 MB
# // Time Limit : 1000 ms
# // Powered by CP Editor (https://github.com/cpeditor/cpeditor)

dp = [None]*1000010
dp[0] = 0
dp[1] = 1	
MOD = 15746
n = int(input())
for i in range(2,n+2):
	dp[i] = (dp[i-1]+dp[i-2])%MOD
print(dp[n+1])

n=int(input())
a,b=1,2
if n==1 :
    print(1)
elif n==2 :
    print(2)
else :
    for i in range (3 , n+1) :
        c=(a+b)%15746
        a=b
        b=c
    print(c%15746)

n = int(input())

l1 = 1
l2 = 1

ans = 0

if(n == 0):
    ans = 0
elif(n == 1):
    ans = 1
elif(n == 2):
    ans = 2
else:
    ans = 2
    for i in range(3,n+1):
        ans = ans % 15746
        k = l2 
        l2 = ans
        l1 = k
        ans = l1 + l2

ans = ans % 15746
        
print(ans)


'''def abcd(n):
    x=(1+math.sqrt(5))/2
    y=(1-math.sqrt(5))/2
    
    val=((power(x, n, 15746)-power(y, n, 15746))//math.sqrt(5))
    return(int(val))'''
    
def main():
    n=int(input())
    #x=abcd(n+1)
    a=1;    b=2;
    if(n==1):
        print(1)
    elif(n==2):
        print(2)
    else:
        for i in range(3, n+1):
            temp=(a+b)%15746
            a=b%15746
            b=temp%15746
            
        print(temp%15746)
        #print(power(0.55, 67, 1355))
        
main()