Binary password#7438

Binary password

1 saniye
128 megabayt
Çok kolay

Jomart uses a binary string as the password for his computer. Recently, he forgot his old password and now wants to obtain a new one, which will be a binary string of length . He considers a password sufficiently secure if it does not contain two consecutive zeros.

To obtain a new password, Jomart generates a random binary string of length . If the string is not secure, he generates another one and repeats the process until he obtains a secure password.

Find the expected number of randomly generated passwords Jomart will need before he finds a secure one.

Giriş

One integer n~(1 \le n \le 60).

Çıktı

Print the expected value as a fraction , where and are coprime positive integers.

Örnekler

Örnek 1

Loading
Loading

Örnek 2

Loading
Loading