Counting Labeled Trees with Consecutive Neighbour Constraint

Given an integer n, count the number of different labeled (unrooted) trees on n nodes (with nodes labeled 1 through n) satisfying the following condition: for every vertex x there exists a vertex y such that there is an edge between x and y and |x - y| = 1.

In other words, for every vertex x the tree must contain at least one edge joining x and one of its consecutive numbers (either x-1 or x+1). Notice that this forces the edge (1,2) to appear (since vertex 1 only has 2 as a candidate) and the edge (n-1,n) to appear (since vertex n only has n-1 as candidate). For every other vertex i (with 2 ≤ i ≤ n-1) at least one of the edges (i-1,i) or (i,i+1) must be present in the tree.

The answer can be very large; therefore output it modulo \(998244353\).

Note: Since the total number of trees on n labeled nodes is given by Cayley’s formula \(n^{n-2}\), here we are only counting those trees that also satisfy the consecutive neighbor condition.

inputFormat

The input consists of a single integer n (2 ≤ n ≤ 7). Note that to pass all the test cases the solution must work for small n (the intended solution uses brute‐force enumeration over all spanning trees of the complete graph on n vertices).

outputFormat

Output a single integer representing the number of labeled trees satisfying the condition, modulo \(998244353\).

sample

2

1