Perfect Color Scheme

In this problem, a promotional brochure features a giant artwork made by a very peculiar painting process that combines art and technology. The process is as follows:

First, the staff draws \(n!\) independent point grids. Each grid is an \(n \times 2\) array of points. In the \(i\)-th grid, the set of points is defined as \(X_i\cup Y_i\), where \(X_i = \{(0,y)\mid y \in \{0,1,\dots, n-1\}\}\) and \(Y_i = \{(1,y)\mid y \in \{0,1,\dots, n-1\}\).

Then, let \(\Sigma = \{\sigma_i\}_{i=1}^{n!}\) be the set of all permutations of \(\{0,1,\dots, n-1\}\), listed in lexicographic order. For the \(i\)-th grid, the staff uses the \(i\)-th smallest permutation \(\sigma_i\) to connect the points in \(X_i\) and \(Y_i\) by straight line segments; for every \(P=(0,y) \in X_i\), a segment is drawn connecting \(P\) and \(Q=(1,\sigma_i(y)) \in Y_i\).

Finally, the coloring step is performed. For each grid \(i\) and each \(P=(0,y) \in X_i\), one must choose an arbitrary polyline (which may be a single line segment) along the drawn segments to reach any point in \(Y_i\) and color the entire chosen path with the \(y\)-th color. In doing so, it is required that in every grid, the total length of any drawn line segment that is colored with more than one color is \(0\) (i.e. no segment is colored overlappingly by different colors).

It turns out that the only valid way to achieve the non-overlapping condition is, for each grid, to simply color each drawn segment (from \((0,y)\) to \((1,\sigma_i(y))\)) entirely with the designated color. Two coloring schemes are considered different if and only if there exists some grid \(i\) and some point \(P\) such that the set of colors covering \(P\) is different between the two schemes.

Since every grid has exactly one valid coloring, the total number of valid coloring schemes is \nolinebreak\(1^{n!} = 1\). You only need to output this number modulo \(p=335544323\) (which is, of course, \(1\) modulo \(335544323\)).

inputFormat

The input consists of a single integer \(n\) \((1 \le n \le 10^5)\), which describes the dimensions of each grid.

outputFormat

Output a single integer --- the number of valid coloring schemes modulo \(335544323\).

sample

1

1