408656: GYM103256 E2 Coins Game (hard version)

Memory Limit:64 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E2. Coins Game (hard version)time limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

This is the hard version of this problem. The only difference is the constraint of $$$n$$$.

Palindromito is playing with his new $$$n$$$ coins, all of them are lined up on his desk numbered from $$$1$$$ to $$$n$$$, each showing Águila ($$$A$$$) or Sol ($$$S$$$). The goal of the game is to finish with all the coins showing Sol, and the only possible move is: if there are $$$k$$$ coins showing Águila and $$$k \geq 1$$$, then he flips the $$$k^{th}$$$ coin over; otherwise the game ends.

For example, if he start with 3 coins showing $$$SAS$$$, in 3 steps he finishes the game: $$$SAS \to AAS \to ASS \to SSS$$$. It can be shown that for any configuration of $$$n$$$ coins, the number of steps until the game is over is always finite.

Palindromito wants to find the average number of steps over all $$$2^n$$$ possible configurations of his coins, please help him. This value is always a rational number.

Input

In the only line you'll be given the positive integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$).

Output

Suppose that the answer has the form $$$\frac{a}{b}$$$, where $$$a,b>0$$$ are positive integers and $$$\gcd(a,b)=1$$$. Print $$$a/b$$$, i.e., the two numbers separated by a slash $$$/$$$.

ExamplesInput
1
Output
1/2
Input
2
Output
3/2
Input
3
Output
3/1

加入题单

上一题 下一题 算法标签: