Daniel 正在尝试洗一副包含 $n$ 张不同卡牌的牌组。为此，他发明了一种新的洗牌操作，他将其称为“Julienning”。

首先，他选择一个整数 $i$，$1 \le i < n$。然后，他同时翻转牌组的前 $i$ 张牌和后 $n - i$ 张牌。

例如，如果他的牌组初始排列为 $p = [1, 4, 3, 2, 5, 6]$，那么在进行 $i = 4$ 的 Julienne 操作后，牌组变为 $p' = [2, 3, 4, 1, 6, 5]$。

如果 Daniel 从一副有序的 $n$ 张卡牌开始，通过任意次数（可能为零）的 Julienne 操作，他能得到多少种不同的牌组排列？

由于答案可能很大，请输出其对 $998244353$ 取模的结果。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 10^{12}$)，表示牌组中卡牌的数量。

输出格式

输出一个整数，表示可达到的排列数量，对 $998244353$ 取模。

样例

输入 1

1

输出 1

1

输入 2

1000000000000

输出 2

516560941

输入 3

3

输出 3

6