eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Заготовка грибов

Заготовка грибов

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Белочка осенью готовится к предстоящей зиме и занята заготовкой грибов. Собирает она только белые грибы и подберезовики, потом нанизывает их на связку и вешает на дереве для просушки. При этом Белочка хочет, чтобы на каждой связке было ровно N грибов, все связки были разными и при этом чтобы в любой связке не встречалась последовательность "белый гриб" - "подберёзовик" - "белый гриб".

Сколько связок грибов на предстоящую зиму заготовит Белочка, если в лесу этой осенью грибов достаточно много.

Входные данные

Единственное натуральное число N (N < 10000) – количество грибов в связке.

Выходные данные

Количество связок, которые будут заготовлены Белочкой на зиму. Так как ответ может быть достаточно большим, ответ вывести по модулю 9997.

Пример

Входные данные #1
3
Выходные данные #1
7
Автор А. Присяжнюк