Заготівля грибів

Білочка осінню готується до майбутньої зими і зайнята заготівлею грибів. Збирає вона лише білі гриби і підберезовики, потім нанизує їх на в'язку і вішає на дереві для просушування. При цьому Білочка хоче, щоб на кожній в'язці було рівно N грибів, всі в'язки були різними і при цьому щоб у довільній в'язці не зустрічалась послідовність "білий гриб" - "підберезовик" - "білий гриб".

Скільки в'язок грибів на майбутню зиму заготовить Білочка, якщо у лісу цієї осені грибів достатньо багато.

Вхідні дані

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

Вихідні дані

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

Приклади