Казалось бы, пробки на дорогах — это не проблема для трамваев. Но если пути проходят прямо по проезжей части, то трамвай оказывается на равных с другим транспортом. На самом деле, ему даже хуже — ведь трамвай не может объехать проблемный участок дороги.

Водитель трамвая Зина всегда найдет, чем заняться, пока ее вагон стоит в пробке. Больше всего она любит раскладывать один карточный пасьянс. В нем используется колода, состоящая из карт двух мастей (червей и пик) n различных достоинств (то есть всего 2n карт). Карты берутся из колоды по одной и выкладываются в ряд слева направо рубашкой вниз. После выкладывания каждой карты производится просеивание: если в ряду есть две карты одной масти либо одного достоинства, расположенные через одну, то левая из этих двух карт удаляется, а все карты правее нее сдвигаются на одну влево. При этом если таких пар несколько, то выбирается та, которая находится ближе к началу ряда. Просеивание производится многократно, пока в ряду есть такие пары. Пасьянс сошелся, если после выкладывания всей колоды и просеивания в ряду осталось ровно две карты.

Например, если в определенный момент в ряду были карты «H7 S5 S2 H4» («H» обозначает черви, «S» — пики), и к ним добавилась «S7», то после первого просеивания получится «H7 S5 H4 S7». Далее из двух пар «просеивается» первая, и остается «S5 H4 S7». И, наконец, после очередного просеивания получаем «H4 S7».

Зине всегда было интересно, каков шанс, что пасьянс сойдется. Сможете ли вы ответить на этот вопрос?

В единственной строке записано целое число n, 2 ≤ n ≤ 10000.

Выведите вероятность того, что пасьянс сойдется, в виде несократимой дроби. Используйте формат, приведенный в примере.