No.1879 How many matchings?
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 52
作問者 :
37zigen
/ テスター :
shotoyoo
cologne
タグ : / 解いたユーザー数 52
作問者 :
37zigen
/ テスター :
shotoyoo
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。