No.906 Y字グラフ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 72
作問者 : %20%20 / テスター : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
0 ProblemId : 2413 / 出題時の順位表

問題文

木であって、次数 $4$ 以上の頂点が無く、次数 $3$ の頂点がちょうど $1$ 個あるものを「Y字グラフ」と呼ぶことにします。
頂点数が $N$ のY字グラフの種類数を $10^9+7$ で割った余りを求めて下さい。

入力

$N$

入力は以下の制約を満たします。

  • $4 \le N \le 10^{18}$
  • $N$ は整数である。

出力

頂点数が $N$ のY字グラフの種類数を $10^9+7$ で割った余りを出力してください。

サンプル

サンプル1
入力
4
出力
1

頂点数 $4$ のY字グラフは下図の $1$ 種類です。Y字グラフには少なくとも $4$ 個の頂点があります。

サンプル2
入力
7
出力
3

頂点数 $7$ のY字グラフは下図の $3$ 種類です。

サンプル3
入力
100
出力
817

サンプル4
入力
314159265358979323
出力
92208567

$N$ が非常に大きい場合があります。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。