Background

我「毁灭」这命运的枷锁——卡厄斯兰那

愿「负世」照拂黎明

Description

众所周知，卡厄斯兰那为了收集火种轮回了33550336次。

某一次轮回，他进入了一片神奇的森林，这里的树叶有一种特殊的力量，每一片树叶会随机选择他收集的一颗火种并熄灭。

但这种树叶不会判断火种是否已经熄灭，因此每次都会在所有火种中等概率随机选择一颗。

现在他想知道熄灭他身上的所有火种需要的树叶数量的期望。

Format

Input

一个整数 $n \ (1 \le n \le 5 \times 10^5)$ 表示卡厄斯兰那的火种数量。

Output

一个整数，表示熄灭 $n$ 个火种需要的树叶数量的期望值对 $998244353$ 取模后的结果。

Samples

1

1

2

3

3

499122182