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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '\r\n# // Problem : Zero One Tiles\r\n# // Contest : CodeChef - IARCS OPC Judge Problems\r\n# // URL : https://www.codechef.com/IARCSJUD/problems/TILES01\r\n# // Memory Limit : 256 MB\r\n# // Time Limit : 1000 ms\r\n# // Powered by CP Editor (https://github.com/cpeditor/cpeditor)\r\n\r\ndp = [None]*1000010\r\ndp[0] = 0\r\ndp[1] = 1\t\r\nMOD = 15746\r\nn = int(input())\r\nfor i in range(2,n+2):\r\n\tdp[i] = (dp[i-1]+dp[i-2])%MOD\r\nprint(dp[n+1])'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 8013115