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

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

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

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

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

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

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

Примеры