题目描述

本题为 HDU 6588 加强版。

给定正整数 $n$，请你求出如下式子的值：

$$ \sum_{i = 1} ^ {n} \gcd\left(\left\lfloor\sqrt[3]{i}\right\rfloor, i\right) $$

答案对 $998244353$ 取模。

输入格式

一行一个正整数 $n$。

输出格式

一行一个整数表示上述式子对 $998244353$ 取模的值。

样例 1

input

987654

output

3595606

样例 2

input

98723489637846786423

output

765547726

数据范围与提示

本题采用捆绑测试。

考虑到 $n$ 的范围超过 long long，因此变量类型需要采用 __int128（其范围是 $[-2 ^ {127}, 2 ^ {127})$）。而 C++ 内并没有兼容 __int128 的输入方式。下面给出用于输入 __int128 的函数：

template <class Tp>
void read(Tp &x) {
    static char ch;
    static bool neg;
    for (ch = neg = 0; ch < '0' || ch > '9'; neg |= (ch == '-'), ch = getchar());
    for (x = 0; ch >= '0' && ch <= '9'; (x *= 10) += (ch ^ 48), ch = getchar());
    neg && (x = -x);
}