{"problem":{"name":"「GLR-R4」大暑","description":{"content":"  “阿绫，你看这宣传册上这幅画，好奇怪呀。”   在宣传册中“融艺术与科技为一体”的巨幅画作的制作过程如下：   首先，工作人员画出 $n!$ 个 $n\\times2$ 的点阵图，任意两个点阵图间互相远离，在后续的制作过程中**互相独立**。对于第 $i$ 个点阵图，令其左下角坐标为 $(0,0)$，该点阵的点集为 $X_i\\cup","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9159"},"statements":[{"statement_type":"Markdown","content":"  “阿绫，你看这宣传册上这幅画，好奇怪呀。”\n\n  在宣传册中“融艺术与科技为一体”的巨幅画作的制作过程如下：\n\n  首先，工作人员画出 $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\\}$。\n\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$ 相连。\n\n  最后，是激动人心的上色步骤。对于第 $i$ 个点阵图中的每个 $P(0,y)\\in X_i$，从 $P$ 出发，沿着上一步骤中作出的线段，走**任意线段或折线**，到达 $Y_i$ 中的任意一点，并为这条线段或折线染上第 $y$ 种颜色。此外，为了避免不同颜色混在一起，需要保证，在所有 $n!$ 个点阵图中，被多余一种颜色染过的线段长度之和为 $0$。\n\n  呈现在天依一行人眼前的这幅画的上色明显很敷衍，所以天依想知道到底有多少种可供选择的上色方案。定义两种上色方案不同，当且仅当存在编号 $i\\in[1,n!]$ 和任意一点 $P$，使得两个上色方案各自完成后，第 $i$ 个点阵图中染过点 $P$ 的颜色集合不同。\n\n  你只需要告诉天依答案对 $p=335~544~323$ 取模后的结果。*天依可是为了简化你的计算，精挑细选了一个有趣的模数呢。*\n\n  （请参考样例 #1 解释确认题意。）\n\n## Input\n\n输入一行一个整数 $n$，表示作画过程的参数。\n\n## Output\n\n输出一行一个非负整数，表示上色方案数对 $p$ 取模的结果。\n\n[samples]\n\n## Background\n\n  「时见疏星落画檐，几点流萤小」\n\n---\n\n  全国音乐祭，在天依一行人抵达之时，芙城早已翻涌这狂欢的气氛，汇聚于此的某些紧张青年人们倒显得有些格格不入。\n\n  “总之，这里一定是终点站吧。”\n\n  排练又一次随着弦音结束。又开始，结束。\n\n  “阿绫，我们出去走走吧。”\n\n---\n\n  **大暑** 「为所有视线涂抹上　一片蔚蓝的颜色　融化了苦涩」\n\n## Note\n\n#### 样例 #1 解释\n\n在完成前两步后，画作的全貌如下。$(A,B,C,D,E,F)$ 构成一组 $n\\times2$ 的点阵图，不同点阵图的相对位置并不重要。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/6xaw4brz.png)\n\n以下是一种可供选择的染色方案。红、黄、蓝依次对应第 $0,1,2$ 种颜色。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ma3r8yit.png)\n\n#### 样例 #2 解释\n\n答案的真实值为 $996~124~179~980~315~787~264$。\n\n### 数据规模与约定\n\n对于 $100\\%$ 的数据，$n\\le10^6$。\n\n对于不同的子任务，作如下约定：\n\n| 子任务编号 |       $n$        | 子任务分值 |\n| :--------: | :--------------: | :--------: |\n|    $1$     |      $\\le9$      |    $10$    |\n|    $2$     |     $\\le100$     |    $10$    |\n|    $3$     |     $\\le500$     |    $15$    |\n|    $4$     | $\\le5\\times10^3$ |    $20$    |\n|    $5$     |    $\\le10^5$     |    $20$    |\n|    $6$     |    $\\le10^6$     |    $25$    |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9159","tags":["洛谷原创","O2优化","洛谷月赛"],"sample_group":[["3","384"],["4","40344945"]],"created_at":"2026-03-03 11:09:25"}}