题目描述

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

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

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

输入格式

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

输出格式

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

样例 1

5

998244351

987654

445190

数据范围与提示

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