Permutation Order Product

Farmer John has come up with a new exercise routine for his cows! There are (N) cows standing in a line with positions (1,2,\dots, N). For a given permutation (A = (A_1, A_2, \dots, A_N)) of ({1, 2, \dots, N}), the cows rearrange themselves so that the cow that was in the (i)th position (from the left) moves to the (A_i)th position. This process is repeated until the cows return to their original order.

For each permutation (A) of length (N), let the number of steps required to return to the original order be (f(A)) (which equals the least common multiple of the lengths of the cycles when (A) is decomposed into disjoint cycles, i.e. (f(A)=\mathrm{lcm}(\ell_1,\ell_2,\dots,\ell_k))). Your task is to compute the product [ P = \prod_{A \in S_N} f(A)] where the product is taken over all (N!) permutations, and output (P \bmod M).

Here (M) is a prime number satisfying (10^8 \le M \le 10^9+7).

A useful observation is that for any prime (p) and any permutation (A), if we define the (p)–adic valuation of (f(A)) as (v_p(f(A)) = \max_{\text{cycle }C \text{ of }A} v_p(|C|)), then [ \log P = \sum_{p} \Bigl(\sum_{k \ge 1} \Bigl(#{A \in S_N:, f(A) \text{ has } p^k \text{ dividing some cycle length}}\Bigr)\Bigr) \log p. ] You might find it easier to compute, for each prime (p) and exponent (k), the number of permutations in (S_N) that contain at least one cycle of length divisible by (p^k). Note that if we denote by (F_d(N)) the number of permutations in (S_N) that do NOT contain any cycle of length divisible by (d), then for each (d) (where (d=p^k)) the desired count is (N! - F_d(N)).

A standard recurrence for computing (F_d(n)) is: [ F_d(0)=1, \quad F_d(n) = \sum_{\substack{\ell=1\ \ell \not\equiv 0 ; (\bmod, d)}}^{n} \binom{n-1}{\ell-1} (\ell-1)!, F_d(n-\ell)\quad \text{for } n \ge 1. ]

Be sure to use fast modulo operations since some languages (such as C++) may benefit from well‐known optimizations such as Barrett Reduction if needed.

inputFormat

The first and only line of input contains two integers (N) and (M) separated by a space, where (1 \le N \le 50) and (M) is a prime satisfying (10^8 \le M \le 10^9+7).

outputFormat

Output a single integer: the value of (\prod_{A \in S_N} f(A)) modulo (M).

sample

1 1000000007

1