В танцевальном соревновании участвуют $n$ мужчин и $n$ женщин. Соревнование проводится по следующим правилам:

1. Изначально мужчины и женщины случайным образом разбиваются на $n$ пар, и все пары расставляются по кругу.
2. Судья подбрасывает монету и определяет число $k$, которое с равной вероятностью равно 1 или 2. После этого другой бросок монеты определяет направление — «по часовой стрелке» или «против часовой стрелки», также с равной вероятностью.
3. В соответствии с результатами бросков монеты на предыдущем шаге, женщины меняют партнеров, перемещаясь по кругу на $k$ позиций в соответствующем направлении (мужчины при этом остаются на своих местах).
4. Если после перемещения женщина оказывается в паре с мужчиной, с которым она уже танцевала в одном из предыдущих раундов, соревнование заканчивается, и судьи определяют победителей. В противном случае текущие пары танцуют раунд, судьи тщательно оценивают их, и процесс возвращается к шагу 2.

Определите математическое ожидание количества раундов, которые будут станцованы во время соревнования.

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

В единственной строке содержится целое число $n$ ($2 \le n \le 50$).

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

Выведите ответ с точностью $10^{-9}$.

Примеры

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

3

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

2.50000000000000000000

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

5

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

3.21875000000000000000