题目描述

听说刘姥姥是整个红楼里最为精明之人，小码妹决定出道题好好考考她：

定义数列 $f_1 = 1, f_2 = 1, f_i = f_{i-1} + f_{i-2}(i > 2)$，定义函数 $g(x)$ 表示正整数 $x$ 的约数个数。现在给你一个正整数 $n$，请你求值：

$$(\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n g(gcd(i,j,k)) \times gcd(f_i,f_j,f_k)) \mod 998244353$$

其中，$gcd(x,y,z)$ 表示整数 $x,y,z$ 的最大公约数。

输入格式

一行一个整数 $n(1 \leq n \leq 10^6)$。

输出格式

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

5

152

10

1768