AT_pakencamp_2024_day1_h Buttons

$ 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 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $

答えを出力せよ。

### 小課題 1. ( $ 50 $ 点 ) $ N \leq 10^6 $ 2. ( $ 200 $ 点 ) $ N \leq 10^{18} $ 3. ( $ 150 $ 点 ) 追加の制約はない。 ### Sample Explanation 1 例えば、 $ 2 $ 個目のライトが点灯している状態からすべてのライトを点灯させる場合、 $ (1,4) $ に対応するボタンを押した後、 $ (2,2) $ に対応するボタンを押すことで $ 2 $ 回で達成することができます。 ボタンを $ 1 $ 回以下押して $ 2 $ 個目のライトが光っている状態からすべてのライトを点灯させることができないため、ボタンを押す必要がある回数の最小値は $ 2 $ です。 ### Sample Explanation 3 $ 998244353 $ で割ったあまりを求めることを忘れないでください。 ### Constraints - $ 1 \leq N \leq 10^{100000} $ - 入力は全て整数