题目描述

小明想要构造三个分数 $\frac{a}{b}$，$\frac{a}{c}$，$\frac{d}{c}$。

要求涉及到的 $a,b,c,d$ 都必须是 $1\sim n$ 范围内的正整数。且三个分数互相不相等，即 $\frac{a}{b}\neq\frac{a}{c}$，$\frac{a}{b}\neq\frac{d}{c}$，$\frac{a}{c}\neq \frac{d}{c}$。

请求出有多少种构造方法，答案可能很大，请输出其对 $998244353$ 取模后的结果。

提示：由于浮点数不精确，所以在比较 $\frac{a}{b}\neq\frac{x}{y}$ 时，尽量转换为比较 $a\times y \neq x\times b$。

输入格式

一个数 $n$。

输出格式

一个整数，即满足条件的三个分数有多少种方案。

注意：只要两个方案涉及的四个变量 $a,b,c,d$ 有一个不相同，就认为是不同的方案。

2

2

样例解释 1

• $\frac{1}{2},\frac{1}{1},\frac{2}{1}$
• $\frac{2}{1},\frac{2}{2},\frac{1}{2}$

3

30

样例解释 2

• 比如：$\frac{2}{2},\frac{2}{1},\frac{3}{1}$

5

376

33

1111984

样例解释 3

• 比如：$\frac{5}{4},\frac{5}{1},\frac{3}{1}$

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 3333$。

• 子任务 1（30 分）：保证 $n\le 33$。
• 子任务 2（30 分）：保证 $n\le 333$。
• 子任务 3（40 分）：保证 $n\le 3333$。