Binary password

Zhomart uses binary string as a password for his computer. Now he forgot his old password and wants to get a new one, which is a binary string of length $n$. He believes that password is strong enough if it doesn't contain two consecutive zeroes. To get a new password he generates a random binary string of length $n$. If it is not strong he generates a random string again and so on until he finds a strong password. Find the expected number of random passwords Zhomart must generate before he finds strong one.

Input

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

Output

Print the expected number as $p/q$, where $p$ and $q$ are relatively prime positive integers.

Examples