### Indian National Olympiad in Informatics

### Online Programming Contest, 15-16 July 2006

### Basic Division

Problem 1: 0/1 Tiles, *(K Narayan Kumar, CMI)*

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 possiblities: 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 format

A single line with a single integer *N*.

Output format

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

Test data

You may assume that *N* ≤ 1000000.

Example

Here is a sample input and output corresponding to the example
discussed above.

Sample input

4

Sample output

5