Mushroom

Autumn squirrel preparing for the upcoming winter and busy harvesting mushrooms. It collects only the white mushrooms and boletus, then stringing them on a bunch, and hangs on a tree to dry. In this squirrel wants to each bundle was exactly N mushrooms, all the ligaments were different and at the same time that the bundle had not met any sequence of "white fungus" - "boletus"- "white mushroom. "

How many bundles of mushrooms prepared for the coming winter squirrel, if in the woods this fall mushrooms quite a lot.

Input

The only positive integer N (N < 10000) - the number of fungi in the bundle.

Output

Number of ligaments, which will be procured squirrel for the winter. Since the response may be large enough to deduce the answer modulo 9997.

Examples