「GLR-R4」大暑

  「时见疏星落画檐，几点流萤小」 ---   全国音乐祭，在天依一行人抵达之时，芙城早已翻涌这狂欢的气氛，汇聚于此的某些紧张青年人们倒显得有些格格不入。   “总之，这里一定是终点站吧。”   排练又一次随着弦音结束。又开始，结束。   “阿绫，我们出去走走吧。” ---   **大暑** 「为所有视线涂抹上　一片蔚蓝的颜色　融化了苦涩」

  “阿绫，你看这宣传册上这幅画，好奇怪呀。”   在宣传册中“融艺术与科技为一体”的巨幅画作的制作过程如下：   首先，工作人员画出 $n!$ 个 $n\times2$ 的点阵图，任意两个点阵图间互相远离，在后续的制作过程中**互相独立**。对于第 $i$ 个点阵图，令其左下角坐标为 $(0,0)$，该点阵的点集为 $X_i\cup Y_i$，其中 $X_i=\{(0,y)\mid y\in[0,n)\cap\mathbb N\}$，$Y_i=\{(1,y)\mid y\in[0,n)\cap\mathbb N\}$。   接着，设集合 $\Sigma=\{\sigma_i\}_{i=1}^{n!}$ 包含 $\{0,1,\dots,n-1\}$ 的所有 $n$ 阶排列，对于第 $i$ 个点阵图，工作人员将用字典序第 $i$ 小的排列 $\sigma_i$ 为 $X_i,Y_i$ 连线配对：对于点 $P(0,y)\in X_i$，作一条线段将其与点 $Q(1,\sigma_{i,y})\in Y_i$ 相连。   最后，是激动人心的上色步骤。对于第 $i$ 个点阵图中的每个 $P(0,y)\in X_i$，从 $P$ 出发，沿着上一步骤中作出的线段，走**任意线段或折线**，到达 $Y_i$ 中的任意一点，并为这条线段或折线染上第 $y$ 种颜色。此外，为了避免不同颜色混在一起，需要保证，在所有 $n!$ 个点阵图中，被多余一种颜色染过的线段长度之和为 $0$。   呈现在天依一行人眼前的这幅画的上色明显很敷衍，所以天依想知道到底有多少种可供选择的上色方案。定义两种上色方案不同，当且仅当存在编号 $i\in[1,n!]$ 和任意一点 $P$，使得两个上色方案各自完成后，第 $i$ 个点阵图中染过点 $P$ 的颜色集合不同。   你只需要告诉天依答案对 $p=335~544~323$ 取模后的结果。*天依可是为了简化你的计算，精挑细选了一个有趣的模数呢。*   （请参考样例 #1 解释确认题意。）

输入一行一个整数 $n$，表示作画过程的参数。

输出一行一个非负整数，表示上色方案数对 $p$ 取模的结果。

3

384

4

40344945

#### 样例 #1 解释 在完成前两步后，画作的全貌如下。$(A,B,C,D,E,F)$ 构成一组 $n\times2$ 的点阵图，不同点阵图的相对位置并不重要。  以下是一种可供选择的染色方案。红、黄、蓝依次对应第 $0,1,2$ 种颜色。  #### 样例 #2 解释 答案的真实值为 $996~124~179~980~315~787~264$。 ### 数据规模与约定 对于 $100\%$ 的数据，$n\le10^6$。 对于不同的子任务，作如下约定： | 子任务编号 | $n$ | 子任务分值 | | :--------: | :--------------: | :--------: | | $1$ | $\le9$ | $10$ | | $2$ | $\le100$ | $10$ | | $3$ | $\le500$ | $15$ | | $4$ | $\le5\times10^3$ | $20$ | | $5$ | $\le10^5$ | $20$ | | $6$ | $\le10^6$ | $25$ |