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.
One integer n~(1 \le n \le 60).
Print the expected value as a fraction , where and are coprime positive integers.
Örnek 1
Örnek 2