配点 : 100 点
問題文
選手 1, 2, \dots, N 可以得到第 N 将举行一场有 人参赛的比赛。
会场准备了列 0, 1, \dots, N-1 可以得到第 N 列,其中排列的选手表示 i\ (0 \le i \le N - 1) 在该时刻连胜中。 i 比赛开始时,选手按照列
的顺序,从前到后排成选手 0 的顺序。 1, 2, \dots, N 在比赛中,按照以下步骤确定各选手的排名。
当某列恰好有
- 人选手时,该列选手的排名为 1 位。此时,步骤结束。 i 在包含至少 N-i 名选手的列中,选择编号最小的列,列
- 2 将有列中的选手 l 。
- 列 l 开始 2 人从列中退出,并用这 2 人进行比赛。比赛获胜者排在列 l+1 的后面,输者排在列 0 的后面。
- 回到步骤 1。
在本次比赛中进行的比赛次数为 998244353 后求余数。
但是,比赛中不会出现平局。此外,无论每场比赛结果如何,答案都可以确定为唯一。
制約
- N 是一个整数
- 1 \le N \le 10^5
入力
输入是按以下格式从标准输入给出的。
N
出力
打印答案。 来自
入力例 1
3
出力例 1
4
假设编号较小的选手获胜,比赛将按如下方式进行。
| 列 0 | 列 1 | 列 2 | 説明 |
|---|---|---|---|
| \underline{1, 2}, 3 | 選手 1, 2 进行比赛,选手 1 在列 1 排列,选手 2 在列 0 后有 | ||
| \underline{3, 2} | 1 | 選手 3, 2 进行比赛,选手 2 在列 1 排列,选手 3 在列 0 后有 | |
| 3 | \underline{1, 2} | 選手 1, 2 进行比赛,选手 1 在列 2 排列,选手 2 在列 0 后有 | |
| \underline{3, 2} | 1 | 選手 3, 2 进行比赛,选手 2 在列 1 排列,选手 3 在列 0 后有 | |
| 3 | 2 | 1 | 人选手时,该列选手的排名为 1 人选手,因此比赛结束。 |
比赛进行 4 回,因此,4 。
入力例 2
5
出力例 2
26
入力例 3
100000
出力例 3
538161387