Counting Unlabeled Unrooted Trees

Given a positive integer n, count the number of unlabeled and unrooted trees with n nodes. Since the answer can be very large, output the result modulo \(998244353\).

Note: For this problem, you may assume that \(1 \le n \le 20\), so that the enumeration of trees is based on the known sequence A000055 (number of trees on n vertices).

inputFormat

The input consists of a single integer n, representing the number of nodes in the tree.

outputFormat

Output a single integer—the number of unlabeled and unrooted trees with n nodes, taken modulo \(998244353\).

sample

1

1