Заготівля грибів#1981
Восени білка готується до прийдешньої зими, збираючи гриби. Вона збирає лише білі гриби та підберезники, нанизує їх на нитку і вішає сушитися на дерево. Білка хоче, щоб на кожній нитці було рівно грибів, всі нитки були різними, і щоб у жодній з них не зустрічалась послідовність "білий гриб" - "підберезник" - "білий гриб" у будь-якому місці.
Скільки різних ниток з грибами білка може підготувати на зиму, якщо цієї осені у лісі грибів вистачить?
Єдине додатне ціле число (N < 10000) — кількість грибів на одній нитці.
Виведіть кількість різних ниток, які білка може підготувати. Оскільки відповідь може бути дуже великою, виведіть її по модулю .
Приклад 1