题目描述

给你一个长度为 $n$ 的序列 $a$，其中每个元素的值分别为 $1\sim n$，即 $a_1=1,a_2=2,\cdots,a_{n-1}=n-1,a_n=n$

当你选择一个连续的区间 $l\sim r$，其中 $l\leq r$，我们记 $f(l,r)$ 的含义为该区间内的完全平方数的个数。

例如 $f(1,3)=1$，因为 $1\sim 3$ 中只有 $1$ 是完全平方数。同样的 $f(2, 10)=2$，完全平方数分别为 $4,9$ 这两个。

现在你需要求出所有连续区间完全平方数的个数之和。

简单来说即求解

再说的通俗一点，你需要求出

$f(1,1)+f(1,2)+\cdots+f(1,n)+f(2,2)+f(2,3)+\cdots+f(2,n)+\cdots+f(n,n)$

答案对 $998244353$ 取余

输入格式

输入一个整数 $n$。

输出格式

输出一行一个整数代表答案。注意答案需要对 $998244353$ 取余。

4

8

100

13552

1600

13664808

10000000000

166638035

样例 1 解释

由于 $n=4$

• 其中 $f(1,1)$ 就是 $1\sim 1$ 内完全平方数个数，也就是 $1$ 自己。
• $f(1,2)$ 就是 $1\sim 2$ 内完全平方数个数，也就是 $1$ 自己。
• $f(1,3)$ 就是 $1\sim 3$ 内完全平方数个数，也就是 $1$ 自己。
• $f(1,4)$ 就是 $1\sim 4$ 内完全平方数个数，也就是 $1,4$ 。

其余的以此类推，最后答案是 $8$。

提示

• 对于百分之 $30$ 的数据，满足 $1\leq n\leq 300$
• 对于百分之 $60$ 的数据，满足 $1\leq n\leq 3000$
• 对于百分之 $100$ 的数据，满足 $1\leq n\leq 10^{12}$