题目背景

  「时见疏星落画檐，几点流萤小」

---

  全国音乐祭，在天依一行人抵达之时，芙城早已翻涌这狂欢的气氛，汇聚于此的某些紧张青年人们倒显得有些格格不入。

  “总之，这里一定是终点站吧。”

  排练又一次随着弦音结束。又开始，结束。

  “阿绫，我们出去走走吧。”

---

  大暑 「为所有视线涂抹上　一片蔚蓝的颜色　融化了苦涩」

题目描述

  “阿绫，你看这宣传册上这幅画，好奇怪呀。”

  在宣传册中“融艺术与科技为一体”的巨幅画作的制作过程如下：

  首先，工作人员画出 $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$
$3$	$\le500$	$15$
$4$	$\le5\times10^3$	$20$
$5$	$\le10^5$
$6$	$\le10^6$	$25$