题目描述

我们有一个圆形的比萨饼。Snuke想要吃掉它的三分之一，或者尽量接近三分之一。

他决定按照以下方式切割这个比萨饼。

首先，他用刀在比萨饼上进行$N$次切割，将比萨饼切成$N$块。刀可以沿着连接比萨饼中心和比萨饼周围某点的线段进行切割。然而，他非常不擅长处理刀具，所以切割角度是均匀随机的，彼此独立。

然后，他选择一个或多个连续的块，使它们的总面积尽量接近比萨饼的三分之一，并将它们吃掉。（设总面积为x。他选择连续的块，使得$|x - 1/3|$最小。）

找出$|x - 1/3|$的期望值。可以证明，这个值是一个有理数，并请按照说明打印出模$10^9 + 7$的结果。

说明

当打印有理数时，首先将其表示为$\\frac{y}{x}$的形式，其中$x, y$为整数且$x$不可被$10^9 + 7$整除（在问题的约束条件下，这种表示总是可能的）。然后，你需要打印出仅满足$xz \\equiv y \\pmod{10^9 + 7}$的整数$z$，其中$z$的范围是$0$到$10^9 + 6$。

约束条件

• $2 \leq N \leq 10^6$

输入

输入以以下格式从标准输入给出：

$N$

输出

按照说明，打印$|x - 1/3|$的期望值模$10^9 + 7$。

示例输入1

2

示例输出1

138888890

期望值是$\\frac{5}{36}$。

示例输入2

3

示例输出2

179012347

期望值是$\\frac{11}{162}$。

示例输入3

10

示例输出3

954859137

示例输入4

1000000

示例输出4

44679646