Spanning Tree Weight Sum with Perfect Square Edge Condition

You are given n vertices numbered from 1 to n. Every unordered pair of distinct vertices (x, y) is connected by an edge. The weight of the edge connecting x and y is determined as follows:

If \(x \times y\) is a perfect square (i.e. there exists an integer \(z\) such that \(z^2 = x \times y\)), then the edge weight is 1; otherwise, it is 0.

A spanning tree is chosen from this graph with the additional condition that for every vertex except vertex 1, there is at least one adjacent vertex with a smaller label. In other words, for every vertex \(i\) (\(2 \le i \le n\)) there must exist a vertex \(j\) (\(1 \le j < i\)) such that the edge between \(i\) and \(j\) is in the spanning tree.

For each possible total edge weight sum \(S\) (where \(0 \le S \le n-1\)) of such a spanning tree, count the number of valid spanning trees that have that sum. Since the answer can be large, output each count modulo 998244353.

Note: Each spanning tree that meets the condition can be uniquely represented by assigning, for every vertex \(i\) (2 \(\le\) i \(\le\) n), a parent vertex \(f(i)\) with \(1 \le f(i) < i\). The weight contribution for vertex \(i\) is 1 if \(f(i) \times i\) is a perfect square, and 0 otherwise.

The answer for each \(S\) should be printed as a sequence of \(n\) space‐separated integers, where the \(k\)th integer corresponds to the number of trees with total edge weight sum equal to \(k\) (with \(k\) from 0 to \(n-1\)).

inputFormat

The input consists of a single integer n (\(2 \le n \le N\)) on a line.

outputFormat

Output \(n\) space‐separated integers. The \(k\)th integer (0-indexed, for \(k=0,1,\ldots,n-1\)) is the number of valid spanning trees whose total edge weight sum is \(k\), taken modulo 998244353.

sample

2

1 0