Білочка осінню готується до майбутньої зими і зайнята заготівлею грибів. Збирає вона лише білі гриби і підберезовики, потім нанизує їх на в'язку і вішає на дереві для просушування. При цьому Білочка хоче, щоб на кожній в'язці було рівно \textbf{N} грибів, всі в'язки були різними і при цьому щоб у довільній в'язці не зустрічалась послідовність "білий гриб" - "підберезовик" - "білий гриб". Скільки в'язок грибів на майбутню зиму заготовить Білочка, якщо у лісу цієї осені грибів достатньо багато. \InputFile Єдине натуральне число \textbf{N} (\textbf{N} < \textbf{10000}) -- кількість грибів у в'язці. \OutputFile Кількість в'язок, які будуть заготовлені Білочкою на зиму. Так як відповідь може бути достатньо великою, відповідь вивести по модулю \textbf{9997}.