01 Tiles

Interview

Time limit0.75sMemory limit256 MB

Summary
Count length-N binary strings tileable by '1' and '00' pieces, modulo 15746, which reduces to a Fibonacci recurrence.
Level

Easy3 of 10

Topics
Dynamic programming, Math
Solved
No attempts yet

Problem

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.

Input

The first line contains a natural number N.

1 <= N <= 1,000,000

Output

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

Examples1

  1. Example 1

    Input
    4
    Expected output
    5