题目描述

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

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

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

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

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

输入格式

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

$N$

输出格式

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

题目大意

有一个圆比萨要切成 $n$ 块，每刀是一条半径。由于你技术不好，你只会独立均匀地随机 $n$ 个角度来切。切完之后你会取出圆上相邻的若干块吃掉。

设这个比萨的面积为 $1$ ，你要找到面积最接近 $\frac{1}{3}$ 的这若干块，即设你取出的面积为 $x$，你想要找到 $\lvert x-\frac{1}{3} \rvert$ 最小的一种方案。求这个最小值的期望，对 $10^9+7$ 取模。

$2\le n\le 10^6$

2

138888890

3

179012347

10

954859137

1000000

44679646

提示

注記

有理数を出力する際は、まずその有理数を分数 $\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$

Sample Explanation 1

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

Sample Explanation 2

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