Mushroom#1981
In autumn, the squirrel prepares for the upcoming winter by harvesting mushrooms. It collects only white mushrooms and boletes, strings them together, and hangs them on a tree to dry. The squirrel wants each string to contain exactly mushrooms, all strings to be different, and for no string to contain the sequence "white mushroom" - "bolete" - "white mushroom" anywhere.
How many different strings of mushrooms can the squirrel prepare for the winter, assuming there are enough mushrooms in the forest this autumn?
The only positive integer (N < 10000) — the number of mushrooms on a string.
Output the number of different strings the squirrel can prepare. Since the answer may be very large, output it modulo .
Example 1