게으른 학생

알고리즘 수업 시험이 곧 치러지며, 응시할 수 있는 날이 $k$일 있다. 합격할 때까지 날들의 임의의 부분집합에 응시하러 가도 된다. 너구리는 게으른 학생이고, 반드시 합격하고 싶지만 배우는 주제는 가능한 한 적게 하고 싶다. 시험 날이 하루만 남았다면 모든 주제를 배워야 한다. 응시 기회가 10번이라면 주제의 3분의 1만 배워도 충분할지도 모른다.

과정을 자세히 설명하면 다음과 같다. 모든 주제는 구간 $[0,1]$이다. 너구리는 처음 $x$개의 주제를 배우며, 여기서 $x$는 0부터 1까지의 실수이다. 시험 날에 응시하면 $x$의 확률로 합격한다. 너구리는 시험 전이나 불합격 사이에 주제를 더 배울 수 있고, 배운 내용은 잊지 않는다. 예를 들어 첫 시험 날 전에 $\frac{1}{3}$을 배우고, 불합격한 뒤에 $\frac{1}{6}$을 더 배우면 총 $\frac{1}{2}$이 된다. 마지막 날 전까지 계속 불합격하면, 반드시 합격하려는 너구리는 마지막 응시 전에 모든 주제를 배운다.

너구리는 많이 배우고 싶어 하지 않는다. 배워야 하는 주제의 기댓값이 가장 작아지는 전략을 고른다. 이 기댓값은 얼마인가?

정수 $k$ 하나가 주어진다. 이는 시험에 응시할 수 있는 횟수이다 ($1 \le k \le 10^{18}$).

답은 기약분수 $\frac{P}{Q}$로 나타낼 수 있다. $P \bmod M$과 $Q \bmod M$을 공백으로 구분해 출력한다. 단, $M = 1\,000\,000\,007$이다.

첫 번째 입력(시험 날이 $2$일뿐인 경우)에서 너구리는 첫 응시 전에 전체 주제의 $\frac{1}{2}$을 배울 수 있다. 첫날 불합격하면 나머지 $\frac{1}{2}$을 더 배운다. 따라서 배워야 할 주제의 기댓값은 $\frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot 1 = \frac{3}{4}$이다.