No.554 recurrence formula

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 111
作問者 : addeight2addeight2 / テスター : mai(舞葉)mai(舞葉)

0 ProblemId : 1287 / 出題時の順位表

問題文

次の漸化式で定義される数列{a}の第n項目を$10^9+7$で割った余りを求めてください
$a_1=1$
nが1以外の時
nが偶数ならば$a_n=n*(a_1+a_3+a_5+・・・+a_{n-1})$
nが奇数ならば$a_n=n*(a_2+a_4+a_6+・・・+a_{n-1})$

入力

n

$ 1 \le n \le 10^5 $

出力

数列{a}の第n項を$10^9+7$で割った余りを出力してください 最後に改行してください。

サンプル

サンプル1
入力
2
出力
2

$a_2 = 2 * a_1 = 2$

サンプル2
入力
4
出力
28

$a_4 = 4 * (a_1 + a_3) = 28$

サンプル3
入力
6
出力
942

$a_6 = 6 * (a_1 + a_3 + a_5) = 942$

提出ページヘ