暂无测试数据。

Description

We call a set of nodes \(S\) a clique of the given graph \(G\), if and only if all nodes in \(S\) are pairwise connected with a edge.

Your task is to determine the maximum number of maximum cliques in a graph with \(n\) nodes.

Input

The only line of input contains a single integer \(n\).

Output

Print the answer. Since it can be tremendulous, print it taken modulo \(998244353\).

Examples

Sample Input

8

Sample Output

18