Keenan got an undirected clique for his birthday! As part of his birthday present, he gets to direct the edges in his clique!

Keenan hates triangles. He has decided to direct the edges of his clique such that there is a minimum number of triangles, but he's not sure how. Can you help him?

Note: A triangle is a set of distinct vertices ~(a, b, c)~ such that ~a~ is reachable from ~b~, ~b~ is reachable from ~c~, and ~c~ is reachable from ~a~.

Constraints

~1 \le N \le 50~

In tests worth 14 marks, ~N \le 6~.

Input Specification

The first and only line contains one integer ~N~, the number of vertices in Keenan's clique.

Output Specification

Let ~T~ be the minimum number of triangles that can be obtained over all possible ways of directing the edges. Output ~W~, the number of ways to orient the edges in the clique such that the resulting graph has exactly ~T~ triangles. Because ~W~ may be large, output it modulo 998244353.

Sample Input

1

Sample Output

1