配点 : $1800$ 点

問題文

円形のピザがあります。 すぬけ君は、なるべくこのピザの $1/3$ に近い分量食べたいです。

すぬけ君は、以下のようにピザを切って食べることにしました。

まず、すぬけ君はピザに $N$ 回ナイフを入れて $N$ 個のピースに分割します。 ナイフを入れると、ピザの中心とピザの周上の点を結ぶ線分に沿ってピザに切れ込みが入ります。 ただし、すぬけ君はピザを切るのがとても下手なので、線分の角度は一様ランダムであり、毎回独立であるものとします。

次に、すぬけ君は一個以上のいくつかの 連続する ピースをなるべく合計量が $1/3$ に近くなるように選んで食べます。 (合計量を $x$ とすると、 $|x - 1/3|$ が最小となるように連続するピースを選びます。)

このとき、 $|x - 1/3|$ の期待値を求めてください。 この値は有理数となることが示せます。これを注記で述べるように mod $10^9 + 7$ で出力してください。

注記

有理数を出力する際は、まずその有理数を分数 $\frac{y}{x}$ として表してください。ここで、$x, y$ は整数であり、$x$ は $10^9 + 7$ で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。そして、$xz \equiv y \pmod{10^9 + 7}$ を満たすような $0$ 以上 $10^9 + 6$ 以下の唯一の整数 $z$ を出力してください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$N$

出力

$|x - 1/3|$ の期待値を注記で述べるように mod $10^9 + 7$ で出力せよ。

2

138888890

期待値は $\frac{5}{36}$ です。

3

179012347

期待値は $\frac{11}{162}$ です。

10

954859137

1000000

44679646