01 Tiles

There are two kinds of tiles: a length-1 tile with the digit 1, and a length-2 tile with the digits 00. By placing any number of these tiles from left to right, you can form a binary sequence.

Given N, count how many binary sequences of length N can be formed this way. Assume that there are enough tiles of each kind.

For instance, when N = 1, only 1 can be formed. When N = 2, 00 and 11 can be formed, while 01 and 10 cannot. When N = 4, there are 5 possible sequences, such as 0011, 0000, 1001, 1100, and 1111.

The first line contains a natural number N.

1 <= N <= 1,000,000

Print the number of binary sequences of length N that can be formed, modulo 15746.