eolymp
bolt
Try our new interface for solving problems
Problems

Exercise (Platinum)

Exercise (Platinum)

Time limit 1 second
Memory limit 512 MiB

Farmer John has come up with a new morning exercise routine for the cows (again)!

As before, Farmer John's n cows are standing in a line. The i-th cow from the left has label i for each i (1in). He tells them to repeat the following step until the cows are in the same order as when they started.

Given a permutation A of length n, the cows change their order such that the i-th cow from the left before the change is A[i]-th from the left after the change.

For example, if A = (1, 2, 3, 4, 5) then the cows perform one step and immediately return to the same order. If A = (2, 3, 1, 5, 4), then the cows perform six steps before returning to the original order. The order of the cows from left to right after each step is as follows:

0 steps: (1, 2, 3, 4, 5)

1 step: (3, 1, 2, 5, 4)

2 steps: (2, 3, 1, 4, 5)

3 steps: (1, 2, 3, 5, 4)

4 steps: (3, 1, 2, 4, 5)

5 steps: (2, 3, 1, 5, 4)

6 steps: (1, 2, 3, 4, 5)

Compute the product of the numbers of steps needed over all n! possible permutations A of length n.

As this number may be very large, output the answer modulo m.

Contestants using C++ may find the following code from KACTL helpful. Known as the Barrett reduction, it allows you to compute a % b several times faster than usual, where b > 1 is constant but not known at compile time. (we are not aware of such an optimization for Java, unfortunately).

#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
}

Input data

The first line contains n (1n7500) and m (10^8m10^9 + 7, m is prime).

Output data

Print a single integer.

Example

For each i (1in), the i-th element of the following array is the number of permutations that cause the cows to take i steps: [1, 25, 20, 30, 24, 20]. The answer is 1^1 * 2^25 * 3^20 * 4^30 * 5^24 * 6^20 = 369329541 (mod 10^9 + 7).

Examples

Input example #1
5 1000000007
Output example #1
369329541
Source 2020 USACO US Open, Platinum