三点リーダって2つセットで使わないといけないらしいですね

問題文

.のみからなる長さ $N$ の文字列 $S$ があります。

文字列に対し、次のような操作を考えます。

・その文字列の部分文字列であり...であるようなものを $1$ つ選び、…(...とは異なること、 $1$ 文字であることに注意してください)に置き換えます。そのような部分文字列がない場合、操作は行えません。

$S$ にこの操作を任意の非負整数回行って得られる全ての異なる文字列 $T$ に対し、次の問題を解き、その答えの総和を $998244353$ で割った余りを出力してください。

・ $T$ の部分列として考えられるものは $2^{|T|}$ 通りありますが、そのうち「その文字列に含まれる任意の…に対し、その文字に隣り合う文字のうちちょうど $1$ つが…である」を満たすものはいくつありますか？

制約

• $N$ は整数
• $1\leq N\leq 10^{18}$

入力

N

出力

問題文の通りに出力してください。

サンプル

4

20

文字列 $T$ としてありうるものは、....,.#,#.の $3$ 通りです(ただし、…を#と表記しています)。このうち、条件が満たされる部分列の個数はそれぞれ $16,2,2$ 通りなので、答えは $20$ になります。

6

98

文字列 $T$ としてありうるものは、......,#...,.#..,..#.,...#,##の $6$ 通りです。ここで、##という文字列は##という部分列も条件を満たします。

12345678901234567

930548119

$998244353$ で割った余りを出力してください。