問題一覧 > 通常問題

No.1879 How many matchings?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 53
作問者 : 37zigen37zigen / テスター : shotoyooshotoyoo 👑 colognecologne
5 ProblemId : 7647 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-03-19 02:08:49

問題文

頂点 $1$、頂点 $2$、...、頂点 $n$ からなり、$|a-b| \leq 2$ を満たす任意の相異なる頂点 $a, b$ が一つの辺で接続された無向グラフを $G$ とします。この他に辺はありません。
$G$ の最大マッチングの取り方は何通りあるでしょうか。$10^9+7$ で割った余りを求めてください。

入力

$n$

$1 \leq n \leq 10^{18}$

出力

最大マッチングの取り方の数を $10^9+7$ で割った余りを求めてください。 最後に改行してください。

サンプル

サンプル1
入力
1
出力
1

サンプル2
入力
2
出力
1

サンプル3
入力
10
出力
8

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