Description

最近，肖敏学长在准备数学竞赛，他发现一个正整数可以分解为若干个正整数的平方和。记$f(x)$为$x$最少可以被分解为$f(x)$个正整数的平方和。特别地,$f(x^2)=1$。

例如：$7=2^2+1^2+1^2+1^2$，且不存在$\le 3$个正整数的平方和为$7$，所以$f(7)=4$。\

求$\prod \limits_{i=1}^{n} f(i)\bmod{998244353}$.

Input Format

一行一个正整数$n（1<=n<=100000）$

Output Format

输出一行一个整数。

4

6

27

936673279