Феофан, новый ученик Цыфиркина, оказался намного умнее и сообразительнее Митрофанушки. За первые три урока арифметики он уже научился складывать целые положительные числа в столбик — не очень быстро, зато без ошибок. Для этого Феофан использует следующий алгоритм.

1. Феофан складывает числа поразрядно справа налево: сначала единицы, потом десятки и т.д.
2. Феофан берёт пару цифр в очередном разряде и складывает их.
3. Если происходит перенос единицы из предыдущего разряда, Феофан прибавляет её к полученной сумме.
4. Он приписывает последнюю цифру суммы к ответу и, если необходимо, делает пометку о переносе единицы в следующий разряд.
5. Если разряды закончились, а из последнего разряда есть перенос единицы, Феофан просто приписывает её слева к ответу.

Чтобы написать одну цифру или поставить пометку о переносе единицы, Феофану нужна одна секунда. Если хотя бы одно из складываемых чисел равно нулю или единице, то Феофан тратит на сложение одну секунду, а если оба числа больше единицы — две секунды. Однако, сложив два числа, Феофан запоминает результат сложения и впоследствии в случае надобности вспоминает его за одну секунду. Если Феофану потребуется вычислить a + b и до этого он уже вычислял b + a, то он также сможет использовать полученный ранее результат. К сожалению, к следующему уроку Феофан забывает все эти результаты и ему приходится запоминать их заново.

Например, на сложение чисел 526 и 625 Феофан тратит 12 секунд: четыре секунды — на запись цифр ответа, две секунды — на пометки о переносе, две секунды — на вычисление каждой из сумм 6 + 5 и 2 + 2 и по одной секунде на вычисление сумм 4 + 1 и 5 + 6 (поскольку в процессе сложения Феофан уже запомнил, что 6 + 5 = 11).

В начале очередного занятия Цыфиркин написал на доске два k-значных числа и дал Феофану задание сложить их. Каждое из этих чисел Цыфиркин выбрал равновероятно из множества положительных k-значных чисел без ведущих нулей. Найдите математическое ожидание времени, которое понадобится Феофану для сложения этих чисел.

В единственной строке записано целое число k (1 ≤ k ≤ 5000).

Выведите ожидаемое время сложения двух положительных k-значных чисел с абсолютной или относительной погрешностью не более 10⁻⁶.