AI 游戏

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

有 (n) 座塔和 (n) 个机器人，均编号为 (1) 到 (n)。初始时，第 (i) 座塔由第 (i) 个机器人占据。

游戏开始前，先选择一个长度为 (n) 的排列 (p)，再选择一个序列 (a)，其中 (1\le a_i\le n) 且 (a_i\ne i)。

游戏依次进行 (n) 轮。第 (i) 轮中，若机器人 (p_i) 仍在游戏中，它会占领塔 (a_{p_i})，原先占据该塔的机器人失去这座塔；若机器人 (p_i) 已被淘汰，则本轮没有操作。每轮结束后，没有占据任何塔的机器人会被淘汰。

游戏结束后得到序列 (b)，其中 (b_i) 是最终占据塔 (i) 的机器人编号。

求所有合法的 (a) 和所有排列 (p) 能产生的不同序列对 ((a,b)) 的数量，对质数 (M) 取模。

输入格式

一行两个整数 (n,M)。

输出格式

输出一个整数，表示不同序列对 ((a,b)) 的数量对 (M) 取模的结果。

样例输入 1

1 998244353

样例输出 1

0

样例输入 2

2 998244353

样例输出 2

2

样例输入 3

3 998244353

样例输出 3

24

样例输入 4

8 998244353

样例输出 4

123391016

数据范围

对于全部数据，(1\le n\le5000)，(2\le M\le10^9)，(M) 为质数，且 (2^{18}\mid M-1)。

题目来源：Codeforces 1704H1。