No.906 Y字グラフ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 80
作問者 : %20%20 / テスター : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
1 ProblemId : 2413 / 出題時の順位表
問題文最終更新日: 2018-08-15 23:51:48

問題文

木であって、次数 $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$ が非常に大きい場合があります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。