AT_abc387_g [ABC387G] Prime Circuit

Find the number, modulo $ 998244353 $ , of simple undirected connected graphs $ G $ with $ N $ vertices labeled from $ 1 $ to $ N $ that satisfy the following condition: - For every circuit in $ G $ , the number of edges in that circuit is a prime number. Here, a circuit is a closed trail that may pass through the same vertex more than once (but must not use the same edge more than once).

The input is given from Standard Input in the following format: > $ N $

Print the number, modulo $ 998244353 $ , of simple undirected connected graphs $ G $ satisfying the condition.

### Sample Explanation 1 There are four such graphs $ G $ : - The graph with edges $ (1, 2) $ and $ (1, 3) $ - The graph with edges $ (1, 2) $ and $ (2, 3) $ - The graph with edges $ (1, 3) $ and $ (2, 3) $ - The graph with edges $ (1, 2) $ , $ (1, 3) $ , and $ (2, 3) $ ### Constraints - $ N $ is an integer between 1 and $ 2.5 \times 10^5 $ , inclusive.