← 返回题目列表

AtCoder · agc032_f

F. 三分之一

中文机器翻译题面 查看原题

分数: 1800 点

问题陈述

我们有一个圆形披萨。 Snuke 想要吃掉其中的三分之一,或者尽可能接近的东西。

他决定按如下方式切披萨。

首先,他将披萨分成 N 件制作 N 用刀切。刀可以沿着连接比萨饼中心和比萨饼圆周上的某个点的线段进行切割。然而,他不擅长用刀,所以切割都是以均匀随机的角度进行的,彼此独立。

然后,他选择一个或多个 连续 块,使总数尽可能接近披萨的三分之一,然后吃掉它们。 (令总数为 x 的披萨。他选择连续的块,以便 |x - 1/3| 被最小化。)

求期望值 |x - 1/3|。可以证明这个值是有理数,我们要求你打印它的模 10^9 + 7,如注释中所述。

注释

打印有理数时,首先将其写为分数 \frac{y}{x},其中 x, y 是整数并且 x 不能被整除 10^9 + 7 (在问题的约束下,这种表示总是可能的)。 然后,您需要打印唯一的整数 z 之间 0 和 10^9 + 6,包含在内,满足 xz \equiv y \pmod{10^9 + 7}.

约束

  • 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