No.2156 ぞい文字列
タグ : / 解いたユーザー数 150
作問者 :
hibit_at
/ テスター :
kotamanegi
KowerKoint2010
keisuke6
Michirakara
問題文
Discord サーバー「あさかつ」では、コンテストの前に「ぞい」「ぞいぞい」「ぞぞい」等の発言をすることが常習化しています。
このような文字列は「ぞい文字列」と呼ばれます。
ぞい文字列を、以下の性質を満たす文字列として定義します。
- 「ぞ」と「い」のみからなる文字列である。
- 「ぞ」から始まる。
- 「い」を少なくとも一文字含む。
- 「い」が 2 つ連続してはならない。
正整数 $N$ が与えられるので、長さ $N$ のぞい文字列が何通りあるかを 998244353 で割ったあまりを答えてください。
入力
$N$
- $N$ は整数
- $2 \leq N \leq 10^{18}$
出力
整数 $1$ 行で出力してください。 最後に改行してください。
サンプル
サンプル1
入力
2
出力
1
ありえるぞい文字列は「ぞい」しかありません。
サンプル2
入力
4
出力
4
「ぞぞぞい」「ぞいぞい」「ぞぞいぞ」「ぞいぞぞ」の $4$ 通りが考えられます。
サンプル3
入力
100000
出力
56136313
ぞい文字列はそれなりに長いものである可能性があります。
998244353
で割ったあまりを出力してください。
サンプル4
入力
1000000000000000000
出力
332172356
ぞい文字列はとても長いものである可能性があります。
998244353
で割ったあまりを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。