Lazy Student

The Algorithms course exam is coming soon, and there are $k$ days when you can attempt it. You can come on any subset of the days until you finally pass. Raccoon, a young lazy student, definitely wants to pass, but he also wants to learn as few topics as possible. If only one exam day is left, he has to learn all the topics. If there are 10 attempts, he may hope that learning a third of the topics is enough.

Here is the process in detail. All topics form the segment $[0,1]$. Raccoon learns the first $x$ topics, where $x$ is a real number from $0$ to $1$. When he comes to an exam day, he passes with probability $x$. He may learn more topics before the exams or between attempts, and he never forgets what he has learned. For example, he may learn $\frac{1}{3}$ before the first exam day and then $\frac{1}{6}$ after a failure, reaching a total of $\frac{1}{2}$. If he fails on every day before the last one, he learns all the topics before the last attempt, because he definitely wants to pass.

Raccoon does not want to learn much. He chooses the strategy that gives the smallest expected amount of topics he has to learn. What is this expected amount?

A single integer $k$ is given: the number of attempts to pass the exam ($1 \le k \le 10^{18}$).

The answer can be written as an irreducible fraction $\frac{P}{Q}$. Print $P \bmod M$ and $Q \bmod M$ separated by a space, where $M = 1\,000\,000\,007$.

For the first input (when there are just $2$ exam days), Raccoon may learn $\frac{1}{2}$ of all topics before the first attempt, and another $\frac{1}{2}$ if he fails on the first day. The expected amount of topics to be learned is therefore $\frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot 1 = \frac{3}{4}$.