题目描述

有一个圆形的披萨。すぬけ君希望尽可能吃到接近这块披萨 $1/3$ 的份量。

すぬけ君决定按如下方式切披萨并进食：

首先，すぬけ君用刀在披萨上切 $N$ 次，将披萨分成 $N$ 块。每次切刀时，都是从披萨中心到圆周上的某点，切割的角度是均匀随机的，且每次切割相互独立。

接着，すぬけ君会选择一段连续的若干块披萨，使得它们的总量尽可能接近 $1/3$。也就是说，他会选择使得总量为 $x$ 的连续若干块，使 $|x - 1/3|$ 最小。

请你求出 $|x - 1/3|$ 的期望值。已知这个值是有理数。请按照注记中的要求，输出该值对 $10^9 + 7$ 取模的结果。

输入格式

输入为以下格式，从标准输入读入。

$N$

输出格式

请输出 $|x - 1/3|$ 的期望值，按照注记中的要求对 $10^9 + 7$ 取模。

样例 1

输入

2

输出

138888890

样例 2

输入

3

输出

179012347

样例 3

输入

10

输出

954859137

样例 4

输入

1000000

输出

44679646

说明/提示

注记

输出有理数时，首先将其表示为分数 $\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$

样例解释 1

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

样例解释 2

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

由 ChatGPT 4.1 翻译