Farmer John 又为奶牛们想出了一套新的晨练计划！

和之前一样，Farmer John 的 $N$ 头奶牛（$1\le N\le 7500$）排成一行。从左往右数第 $i$ 头奶牛的编号为 $i$（$1\le i\le N$）。他让奶牛们重复执行以下步骤，直到奶牛们的排列顺序与初始状态相同。

• 给定一个长度为 $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 是否有类似的优化）。

#include <bits/stdc++.h>
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) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b; // can be proven that 0 <= r < 2*b
        return 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
}

输入格式

第一行包含 $N$ 和 $M$。

输出格式

一个整数。

样例

样例输入 1

5 1000000007

样例输出 1

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 无额外限制。