配点 : 400 点
問題文
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}
- 所有输入均为整数
小課題
- ( 50 点 ) N \leq 10^6
- ( 200 点 ) N \leq 10^{18}
- ( 150 点)没有额外的限制。
入力
输入将以以下形式通过标准输入给出。
N
出力
打印答案。
入力例 1
4
出力例 1
20
例如, 当2 如果你想从第二个灯亮的状态开始打开所有灯, 按下 (1,4) 对应的按钮后, 按 (2,2) 对应的按钮 可以在 2 次内实现。
按钮 按少于 1 次 2 由于不可能从第一个灯亮的状态开始打开所有灯,因此必须按下按钮的最少次数为 不要忘记除以 2 。
入力例 2
1
出力例 2
1
入力例 3
2025
出力例 3
697188344
998244353 后求余数。 给出了