时空限制

1S/512M

题目描述

apiadu 发现了一个神奇的宝箱，这个宝箱会源源不断地吐出魔法宝石。宝石的生成非常有规律：

1. 第 $1$ 批：吐出 $1$ 颗宝石，等级都是 $1$；
2. 第 $2$ 批：吐出 $2$ 颗宝石，等级都是 $2$；
3. 第 $3$ 批：吐出 $4$ 颗宝石，等级都是 $3$；
4. 第 $4$ 批：吐出 $8$ 颗宝石，等级都是 $4$；

......

以此类推，每一批吐出的数量都是上一批的 $2$ 倍，而宝石的等级都比上一批加 $1$。

这就形成了一长串的宝石队伍，前几颗宝石的等级分别是：$1, 2, 2, 3, 3, 3, 3, 4, \dots$

apiadu 收集了队伍中前 $n$ 颗宝石，他想计算这些宝石总共含有多少“魔法能量”。计算规则如下：

• 每一颗宝石的能量 = 它的等级 $\times$ 它排在第几位 $\times 2$ 。
• 总魔法能量 = 所有 $n$ 颗宝石的能量加在一起。

由于总能量可能非常大，请输出对 $998244353$ 取模的结果。

格式

输入格式

一行一个整数 $n$，表示 apiadu 收集的宝石数量。

输出格式

输出一行一个整数，表示计算出的总魔法能量对 $998244353$ 取模的结果。

样例

样例输入 #1

3

样例输出 #1

22

样例输入 #2

7

样例输出 #2

154

样例解释 #1

前 $3$ 颗宝石的情况如下：

• 第 $1$ 颗：等级为 $1$。能量为 $= 1 \times 1 \times 2 = 2$。
• 第 $2$ 颗：等级为 $2$。能量为 $= 2 \times 2 \times 2 = 8$。
• 第 $3$ 颗：等级为 $2$。能量为 $= 2 \times 3 \times 2 = 12$。

总魔法能量 $= 2 + 8 + 12 = 22$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	$n \le$	分数
$1$	$10^6$	$30$
$2$	$10^{12}$	$70$

对于 $100\%$ 的数据，保证 $1 \le n \le 10^{12}$。