408656: GYM103256 E2 Coins Game (hard version)

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.

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

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 $$$/$$$.

1

1/2

2

3/2

3

3/1