← 返回题目列表

AtCoder · pakencamp_2024_day1_h

H. 按钮

中文机器翻译题面 查看原题

配点 : 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}
  • 所有输入均为整数

小課題

  1. ( 50 点 ) N \leq 10^6
  2. ( 200 点 ) N \leq 10^{18}
  3. ( 150 点)没有额外的限制。

入力

输入将以以下形式通过标准输入给出。

N

出力

打印答案。


入力例 1

4

出力例 1

20

例如, 当2 如果你想从第二个灯亮的状态开始打开所有灯, 按下 (1,4) 对应的按钮后, 按 (2,2) 对应的按钮 可以在 2 次内实现。

按钮 按少于 1 次 2 由于不可能从第一个灯亮的状态开始打开所有灯,因此必须按下按钮的最少次数为 不要忘记除以 2 。


入力例 2

1

出力例 2

1

入力例 3

2025

出力例 3

697188344

998244353 后求余数。 给出了