問題文

N 個のライトと \frac{N(N+1)}{2} 個のボタンがあります。1 \leq l \leq r \leq N を満たすすべての整数の組 (l,r) に対して、 (l,r) に対応するボタンが 1 つずつあります。各ライトは点灯しているか消灯しているかのどちらかです。

(l,r) に対応するボタンを押すと l 個目, l+1 個目, \ldots, r 個目のライトについて点灯している場合は消灯し、消灯している場合は点灯します。このとき、他のライトには何も起きません。

N 個のライトが点灯しているか消灯しているかの状態は 2^N 通りあります。それぞれの状態から N 個すべてのライトを点灯させるためにボタンを押す必要がある回数の最小値の総和を 998244353 で割ったあまりを求めてください。

制約

• 1 \leq N \leq 10^{100000}
• 入力は全て整数

小課題

1. ( 50 点 ) N \leq 10^6
2. ( 200 点 ) N \leq 10^{18}
3. ( 150 点 ) 追加の制約はない。

入力例 1

4

出力例 1

20

例えば、2 個目のライトが点灯している状態からすべてのライトを点灯させる場合、 (1,4) に対応するボタンを押した後、 (2,2) に対応するボタンを押すことで 2 回で達成することができます。

ボタンを 1 回以下押して 2 個目のライトが光っている状態からすべてのライトを点灯させることができないため、ボタンを押す必要がある回数の最小値は 2 です。

入力例 2

1

出力例 2

1

入力例 3

2025

出力例 3

697188344

998244353 で割ったあまりを求めることを忘れないでください。