国際サッカー選手としてのキャリアを終えた Cristiano Ronaldo は、Niue の国民になりたいと考えました。そのためには、Niue の伝統と文化に関する試験に合格しなければなりません。彼は最後の問題以外のすべての問題には簡単に答えましたが、最後の問題ではあなたの助けが必要です。Ronaldo が Niue の国民になるのを手伝ってくれますか？ 最後の問題は次のとおりです。
「正の整数からなる配列 $a_1,a_2,\ldots,a_n$ に対して、その『土着度』を $\sum_{i=1}^{n} a_i\cdot f_i$ と定義します。ここで、$f_0=1$、$f_1=1$ であり、$i\ge 2$ に対して $f_i=a_{i-1}f_{i-1}+f_{i-2}$ です。
また、逆順にした配列よりも辞書順で小さい配列を『ニウエ的』な配列と呼びます。
整数 $m$ が与えられます。土着度が $m$ 以下であるニウエ的な配列がいくつあるかを求めてください。答えを $998\,244\,353$ で割った余りを答えてください。」
入力
最初の行には、1 つの整数 $m$（$1\le m\le 10^{10}$）が含まれます。
出力
配列の個数を $998\,244\,353$ で割った余りを出力してください。
入出力例
入力 1
6
出力 1
1
入力 2
7
出力 2
2
入力 3
13
出力 3
8
入力 4
42
出力 4
114
入力 5
67
出力 5
305
入力 6
6767
出力 6
3471737
入力 7
676767
出力 7
863282261
入力 8
67676767
出力 8
217404956
入力 9
6767676767
出力 9
691869515
注記
