Background

  “Sometimes sparse stars fall on the painted eaves, a few fireflies drifting.”

  At the National Music Festival, by the time Tianyi and her group arrived, Fucheng was already overflowing with a carnival-like atmosphere. Some nervous young people gathered here, however, seemed a bit out of place.

  “Anyway, this must be the terminal station, right?”

  The rehearsal ended once again with the sound of strings. Then it began again, and ended again.

  “A Ling, let’s go out for a walk.”

  Great Heat “Painting every gaze with a patch of blue, melting away the bitterness.”

Problem Description

  “A Ling, look at this painting on the brochure. It’s so strange.”

  In the brochure, the production process of the huge artwork that “combines art and technology” is as follows:

  First, the staff draw $n!$ point-lattice diagrams of size $n\times2$. Any two diagrams are far away from each other, and in the subsequent process they are independent of each other. For the $i$-th diagram, let the bottom-left corner be at $(0,0)$. The set of points in the lattice is $X_i\cup Y_i$, where $X_i=\{(0,y)\mid y\in[0,n)\cap\mathbb N\}$ and $Y_i=\{(1,y)\mid y\in[0,n)\cap\mathbb N\}$.

  Next, let the set $\Sigma=\{\sigma_i\}_{i=1}^{n!}$ contain all permutations of order $n$ of $\{0,1,\dots,n-1\}$. For the $i$-th diagram, the staff use the $i$-th smallest permutation in lexicographic order, $\sigma_i$, to match and connect $X_i$ and $Y_i$: for a point $P(0,y)\in X_i$, draw a line segment connecting it to the point $Q(1,\sigma_{i,y})\in Y_i$.

  Finally comes the exciting coloring step. For each $P(0,y)\in X_i$ in the $i$-th diagram, starting from $P$, follow the line segment drawn in the previous step, travel along any segments or polylines, reach any point in $Y_i$, and color this segment or polyline with the $y$-th color. In addition, to avoid different colors mixing together, it is required that, among all $n!$ diagrams, the total length of segments that have been colored by more than one color is $0$.

  The coloring of the painting shown to Tianyi and her group is clearly very careless, so Tianyi wants to know how many coloring schemes are possible. Define two coloring schemes to be different if and only if there exists an index $i\in[1,n!]$ and some point $P$ such that, after both schemes are completed, in the $i$-th diagram the sets of colors that have colored point $P$ are different.

  You only need to tell Tianyi the result modulo $p=335~544~323$. To simplify your computation, Tianyi carefully chose an interesting modulus.

  (Please refer to Sample #1 explanation to confirm the statement.)

Input Format

Input one line with an integer $n$, representing the parameter of the drawing process.

Output Format

Output one line with a non-negative integer, representing the number of coloring schemes modulo $p$.

3

384

4

40344945

Hint

Sample #1 Explanation

After completing the first two steps, the full picture is as follows. $(A,B,C,D,E,F)$ form one $n\times2$ point-lattice diagram. The relative positions of different diagrams are not important.

The following is one possible coloring scheme. Red, yellow, and blue correspond to the $0,1,2$-th colors respectively.

Sample #2 Explanation

The true value of the answer is $996~124~179~980~315~787~264$.

Constraints

For $100\%$ of the data, $n\le10^6$.

For different subtasks, the constraints are as follows:

Translated by ChatGPT 5