Problem 2. Exercise

USACO 2020 US Open Contest, Platinum

Farmer John（又）想到了一个新的奶牛晨练方案！

如同之前，Farmer John 的 $N$ 头奶牛（$1\le N\le 7500$）站成一排。对于 $1\le i\le N$ 的每一个 $i$，从左往右第 $i$ 头奶牛的编号为 $i$。他告诉她们重复以下步骤，直到奶牛们与她们开始时的顺序相同。

• 给定长为 $N$ 的一个排列 $A$，奶牛们改变她们的顺序，使得在改变之前从左往右第 $i$ 头奶牛在改变之后为从左往右第 $A_i$ 头。

例如，如果 $A=(1,2,3,4,5)$，那么奶牛们总共进行一步就回到了同样的顺序。如果 $A=(2,3,1,5,4)$，那么奶牛们总共进行六步之后回到起始的顺序。每步之后奶牛们从左往右的顺序如下：

• 0 步：$(1,2,3,4,5)$
• 1 步：$(3,1,2,5,4)$
• 2 步：$(2,3,1,4,5)$
• 3 步：$(1,2,3,5,4)$
• 4 步：$(3,1,2,4,5)$
• 5 步：$(2,3,1,5,4)$
• 6 步：$(1,2,3,4,5)$

计算所有可能的 $N!$ 种长为 $N$ 的排列 $A$ 回到起始顺序需要的步数的乘积。

由于这个数字可能非常大，输出答案模 $M$ 的余数（$10^8\le M\le 10^9+7$，$M$ 是质数）。

使用 C++ 的选手可以使用

KACTL

中的这一代码。这一名为

Barrett 模乘

的算法可以以比通常计算快上数倍的速度计算 $a \% b$，其中 $b>1$ 为一个编译时未知的常数。（不幸的是，我们没有找到对于 Java 的这样的优化）。（译注：中文选手可以参考

几种取模优化方法（译自 min-25 的博客）

）

#include 
using namespace std;

typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) <> 64);
        ull r = a - q * b; // can be proven that 0 <= r = b ? r - b : r;
    }
};
FastMod F(2);

int main() {
    int M = 1000000007; F = FastMod(M);
    ull x = 10ULL*M+3; 
    cout << x << " " << F.reduce(x) << "\n"; // 10000000073 3
}

输入格式（文件名：exercise.in）：

输入的第一行包含 $N$ 和 $M$。

输出格式（文件名：exercise.out）：

输出一个整数。

输入样例：

5 1000000007

输出样例：

369329541

对于每一个 $1\le i\le N$，以下序列的第 $i$ 个元素等于奶牛需要使用 $i$ 步的排列数量：$[1,25,20,30,24,20]$。所以答案等于 $1^1\cdot 2^{25}\cdot 3^{20}\cdot 4^{30}\cdot 5^{24}\cdot 6^{20}\equiv 369329541\pmod{10^9+7}$。

注意：这个问题的内存限制增加为 512 MB。

测试点性质： 测试点 2 满足 $N=8$。测试点 3-5 满足 $N\le 50$。测试点 6-8 满足 $N\le 500$。测试点 9-12 满足 $N\le 3000$。测试点 13-16 没有额外限制。

供题：Benjamin Qi