算法课程考试即将到来，总共有 $k$ 天可以尝试通过考试。你可以在直到最终通过考试前的任意天数子集参加考试。年轻的懒学生 Raccoon 一定想要通过考试，但同时他也想学习尽可能少的知识点。这意味着如果只剩下最后一天考试机会，Raccoon 会学习所有的知识点。另一方面，如果有 10 次尝试机会，他可能会希望只学习三分之一的知识点就足够了。

让我们更详细地描述这个过程。设所有知识点为一个区间 $[0, 1]$。Raccoon 学习前 $x$ 个知识点（$x$ 是一个 $0$ 到 $1$ 之间的实数）。当 Raccoon 在考试日参加考试时，他将以概率 $x$ 通过考试。Raccoon 可以在考试前或考试间隙学习任意数量的知识点，直到他通过考试。他永远不会忘记已经学过的知识。例如，Raccoon 可以在第一次考试前学习 $\frac{1}{3}$ 的知识点，如果失败了，再补学 $\frac{1}{6}$，这样总共学习了 $\frac{1}{2}$ 的知识点。如果 Raccoon 在最后一天之前的所有考试中都失败了，他会确保在最后一次尝试前掌握所有知识点（记住，他一定要通过考试）。

Raccoon 很懒，不想学习太多的知识点。他打算选择一种策略，使他需要学习的知识点数量的期望值最小。这个期望值是多少？

输入格式

输入包含一个整数 $k$：参加考试的尝试次数 ($1 \le k \le 10^{18}$)。

输出格式

答案可以表示为一个最简分数 $\frac{P}{Q}$。你需要输出 $P \pmod M$ 和 $Q \pmod M$，中间用空格隔开，其中 $M = 1\,000\,000\,007$。

样例

输入 1

2

输出 1

3 4

输入 2

3

输出 2

39 64

说明

对于第一个输入（当只有 2 个考试日时），Raccoon 可以在第一次尝试前学习所有知识点的 $\frac{1}{2}$，如果第一天失败了，再学习剩下的 $\frac{1}{2}$。因此，需要学习的知识点数量的期望值为 $\frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot 1 = \frac{3}{4}$。