[AdditionalFile6181.zip](file://AdditionalFile6181.zip?type=additional_file)

#6181. 某个套路求和题

标签: 传统 | 时间限制: 1000 ms | 内存限制: 128 MiB |

题目描述

从前有个 alpha1022，他在看某本奇妙的书的时候想到了这样一个函数：

然后就有了这样一个问题：

然后他就把这个问题扔给了你。

输入格式

第一行，一个正整数 $n$。

输出格式

一行一个非负整数，表示答案。

样例 1

输入

5

输出

998244351

样例 2

输入

987654

输出

445190

数据范围与提示

对于 $20\%$ 的数据，$n \le 10^6$；
对于 $40\%$ 的数据，$n \le 10^7$；
对于 $100\%$ 的数据，$n \le 10^{10}$。