No.963 門松列列（2）
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 :
37zigen
/ テスター :
noshi91
タグ : / 解いたユーザー数 19
作問者 :
37zigen
/ テスター :
noshi91
問題文最終更新日: 2020-01-06 13:15:43
Note
この問題はNo.336 門松列列の制約強化版です。問題文
$1$から$N$までの正の整数の並べ替えを順列ですべて行うとき、門松列列になっているものはいくつあるか？$1012924417=483\times 2^{21}+1$で割った余りを答えよ。
ただし、門松列とは$3$つの整数が左から$A$、$B$、$C$と並んでいる時に、全ての値が異なり$A$、$B$、$C$のうち$2$番目に大きな整数が$A$か$C$である場合をいう。
また、どの連続した$3$つの整数を取り出しても門松列になっている数列を門松列列と呼ぶ。
入力
$N$
$3\leq N\leq 202020$
出力
最後に改行してください。
サンプル
サンプル1
入力
3
出力
4
$N=3$のとき門松列列となる順列は、$(1,3,2),(2,1,3),(2,3,1),(3,1,2)$の4つである。
サンプル2
入力
4
出力
10
サンプル3
入力
2016
出力
168501782
原題No.336 門松列列は2016年1月15日に出題された。
サンプル4
入力
2020
出力
360793921
2020年明けましておめでとうございます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。