[R51G]组合数论 - 代码源竞赛平台

时空限制

2.5S/512M

题目描述

计算以下表达式的值：

$$\sum_{i=1}^n \sum_{j=1}^i \operatorname{lcm}(i,j) \times \binom{i}{j}$$

其中 $\operatorname{lcm}(i, j)$ 表示 $i$ 和 $j$ 的最小公倍数，$\binom{i}{j}$ 表示组合数。由于结果可能很大，请对 $998244353$ 取模。

格式

输入格式

第一行包含一个整数 $n$。

输出格式

输出一个整数，表示答案对 $998244353$ 取模后的结果。

样例

样例输入 #1

4

样例输出 #1

129

样例解释 #1

当 $n=4$ 时：

• $i=1$：$\operatorname{lcm}(1,1) \times \binom{1}{1} = 1 \times 1 = 1$
• $i=2$：$\operatorname{lcm}(2,1) \times \binom{2}{1} + \operatorname{lcm}(2,2) \times \binom{2}{2} = 2 \times 2 + 2 \times 1 = 6$
• $i=3$：$\operatorname{lcm}(3,1) \times \binom{3}{1} + \operatorname{lcm}(3,2) \times \binom{3}{2} + \operatorname{lcm}(3,3) \times \binom{3}{3} = 3 \times 3 + 6 \times 3 + 3 \times 1 = 30$
• $i=4$：$\operatorname{lcm}(4,1) \times \binom{4}{1} + \operatorname{lcm}(4,2) \times \binom{4}{2} + \operatorname{lcm}(4,3) \times \binom{4}{3} + \operatorname{lcm}(4,4) \times \binom{4}{4} = 4 \times 4 + 4 \times 6 + 12 \times 4 + 4 \times 1 = 92$ 总和为 $1 + 6 + 30 + 92 = 129$。

样例输入 #2

83444

样例输出 #2

62096447

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$60$	$5000$
$2$	$40$	$10^5$

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$。