举办了一场有 $N$ 名选手的锦标赛，选手编号为 $1, 2, \dots, N$。 赛场设有 $N$ 个队列，编号为 $0, 1, \dots, N-1$。处于队列 $i$ ($0 \le i \le N-1$) 中的选手表示他们此时已经连续赢得了 $i$ 场比赛。 锦标赛开始时，选手们按 $1, 2, \dots, N$ 的顺序排在队列 $0$ 中。 锦标赛根据以下流程确定每位选手的排名：

1. 当每个队列中恰好有一名选手时，队列 $i$ 中选手的排名为 $N-i$。此时流程结束。
2. 在有两个或更多选手的队列中，选择编号最小的队列作为队列 $l$。
3. 队列 $l$ 中的前两名选手离开队列并进行一场比赛。比赛的胜者加入队列 $l+1$ 的末尾，败者加入队列 $0$ 的末尾。
4. 返回第 1 步。

求这场锦标赛中进行的比赛场数，结果对 $998244353$ 取模。 假设比赛中没有平局，并且可以证明无论比赛结果如何，答案都是唯一的。

输入格式

输入通过标准输入给出，格式如下：

$N$

• $N$ 是一个整数。
• $1 \le N \le 10^5$

输出格式

输出答案。

样例

样例输入 1

3

样例输出 1

4

样例输入 2

5

样例输出 2

26

样例输入 3

100000

样例输出 3

538161387

说明

在第一个样例中，假设编号较小的选手赢得比赛，锦标赛的进程如下：

锦标赛共进行了 4 场比赛，因此输出为 4。