Жомарт использует двоичную строку в качестве пароля для своего компьютера. Теперь он забыл свой старый пароль и хочет получить новый, который является бинарной строкой длины . Он считает, что пароль достаточно надежный, если он не содержит двух последовательных нулей. Чтобы получить новый пароль, он генерирует случайную двоичную строку длины . Если он не надежный, то генерирует случайную строку снова и так до тех пор, пока не найдет надежный пароль. Найти ожидаемое число случайных паролей, которое Жомарт должен сгенерировать прежде, чем он найдет надежный.
Одно целое число .
Вывести ожидаемое значение в виде , где и взаимно простые натуральные числа.