ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1615. Трамвайный пасьянс

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Казалось бы, пробки на дорогах — это не проблема для трамваев. Но если пути проходят прямо по проезжей части, то трамвай оказывается на равных с другим транспортом. На самом деле, ему даже хуже — ведь трамвай не может объехать проблемный участок дороги.
Водитель трамвая Зина всегда найдет, чем заняться, пока ее вагон стоит в пробке. Больше всего она любит раскладывать один карточный пасьянс. В нем используется колода, состоящая из карт двух мастей (червей и пик) n различных достоинств (то есть всего 2n карт). Карты берутся из колоды по одной и выкладываются в ряд слева направо рубашкой вниз. После выкладывания каждой карты производится просеивание: если в ряду есть две карты одной масти либо одного достоинства, расположенные через одну, то левая из этих двух карт удаляется, а все карты правее нее сдвигаются на одну влево. При этом если таких пар несколько, то выбирается та, которая находится ближе к началу ряда. Просеивание производится многократно, пока в ряду есть такие пары. Пасьянс сошелся, если после выкладывания всей колоды и просеивания в ряду осталось ровно две карты.
Например, если в определенный момент в ряду были карты «H7 S5 S2 H4» («H» обозначает черви, «S» — пики), и к ним добавилась «S7», то после первого просеивания получится «H7 S5 H4 S7». Далее из двух пар «просеивается» первая, и остается «S5 H4 S7». И, наконец, после очередного просеивания получаем «H4 S7».
Зине всегда было интересно, каков шанс, что пасьянс сойдется. Сможете ли вы ответить на этот вопрос?

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
2
2/3
Автор задачи: Владимир Яковлев
Источник задачи: XII чемпионат Урала по спортивному программированию, 29 марта 2008 г.