题目描述

设集合 $S$ 是 $\N$ 的子集，定义 $f(S)$ 是将 $S$ 中的所有数进行质因数分解后，最小的没有出现的质因数，形式化地，令 $\mathbb{P}$ 是素数集合，$P=\{p\in\mathbb{P}:\exist a\in S,p|a\}$，那么 $\displaystyle f(S)=\min_{p\in\mathbb{P}\setminus P}p$，特别地，如果 $P=\mathbb{P}$，则 $f(S)=\infty$。

已知 $S=\{1,2,\cdots,n\}=\{x\in\N:1\le x\le n\}$，求 $\displaystyle\sum_{T\subseteq S}f(T)$ 对 $998244353$ 取模的值。

输入格式

一行，一个正整数 $n$。

输出格式

一行，一个正整数，表示 $\displaystyle\sum_{T\subseteq S}f(T)$ 对 $998244353$ 取模的值。

2

10

3

24

114

810294897

1001

60225365

提示

样例 $1$ 解释

集合 $S=\{1,2\}$ 的子集有 $\emptyset,\{1\},\{2\},\{1,2\}$，所以答案是 $f(\emptyset)+f(\{1\})+f(\{2\})+f(\{1,2\})=2+2+3+3=10$。

样例 $2$ 解释

集合 $S=\{1,2,3\}$ 的子集有 $\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$，所以答案是 $f(\emptyset)+f(\{1\})+f(\{2\})+f(\{3\})+f(\{1,2\})+f(\{1,3\})+f(\{2,3\})+f(\{1,2,3\})=2+2+3+2+3+2+5+5=24$。

数据范围

对于所有测试数据，保证：$1\le n\le 2000$。

::cute-table{tuack} |测试点编号|$n\le$| |:-:|:-:| |$1\sim 10$|$20$| |$11\sim 30$|$70$| |$31\sim 42$|$150$| |$43\sim 50$|$2000$|