AT_pakencamp_2024_day1_h Buttons

有 $N$ 个灯和 $\frac{N(N+1)}{2}$ 个按钮。对于满足 $1 \leq l \leq r \leq N$ 的所有整数对 $(l, r)$，每个 $(l, r)$ 都对应一个按钮。每个灯要么点亮，要么熄灭。 按下与 $(l, r)$ 对应的按钮时，第 $l$ 个到第 $r$ 个灯会变换状态：如果原来点亮则变为熄灭，原来熄灭则变为点亮。其他灯的状态不变。 $N$ 个灯的状态总共有 $2^N$ 种。对于每一种状态，从该状态变为所有灯全亮，所需最少按按钮次数，求这些最小次数的总和，并对 $998244353$ 取模。

输入从标准输入中给出，格式如下： > $N$

输出答案。

## 子任务 1.（$50$ 分）$N \leq 10^6$ 2.（$200$ 分）$N \leq 10^{18}$ 3.（$150$ 分）没有额外限制。 ## 样例说明 1 例如，如果从第 $2$ 个灯亮着的状态出发，可以先按下 $(1, 4)$ 按钮，再按下 $(2, 2)$ 按钮，这样只需按 $2$ 次就能让所有灯都点亮。 无法通过一次或零次按钮操作使只有第 $2$ 个灯亮着的状态变为全亮，因此最少需要按两次按钮。 ## 样例说明 3 别忘了对 $998244353$ 取模。 # 数据范围 - $1 \leq N \leq 10^{100000}$ - 所有输入均为整数。 由 ChatGPT 5 翻译