D - たのしい式の展開 (Expansion of Equations is Fun)
Earlgray
2
s
1024
MB
600
点
問題文
$\dfrac{(44+\sqrt{2021})^n + (44 - \sqrt {2021})^n}{2\sqrt {2021}}$ の整数部分を $998244353$ で割ったあまりを求めてください。
ヒント
$n\ =\ p\ $のときの答えを$\ A_p\ $として，任意の非負の奇数$\ k\ $について， $$ A_{k+2} \ =\ 88 A_{k+1} + 85 A_{k} + 84 \\ $$ が示せます。制約
- $0 \le n\le 10^{18}$
- $n\ $は整数
小課題
- (20点) $n\le 8$
- (100点) $n\le 10^5$
- (480点) 追加の制約はない
入力
入力は以下の形式で与えられる
$n$
出力
答えを $998244353$ で割ったあまりを出力してください
入力例 1
1
出力例 1
0
$\dfrac{(44+\sqrt{2021}) + (44 - \sqrt {2021})}{2\sqrt {2021}} = \dfrac{44}{\sqrt{2021}}$ の整数部分は $0$ です。
入力例 2
2
出力例 2
88
入力例 3
84569
出力例 3
472414809
答えを $998244353$ で割ったあまりを出力することに注意してください。