Counting Labeled Regular Directed Graphs

Given a positive integer \(n\) and a prime number \(p\), count the number of labeled directed simple graphs on \(n\) vertices satisfying the following conditions:

• For every vertex \(i\) (\(1 \le i \le n\)), the out‐degree and in‐degree are both equal to 2, i.e. \(\deg_{out}(i) = \deg_{in}(i) = 2\).

Recall that a directed simple graph (or digraph) has no self–loops and no multiple edges. However, it is allowed that the two opposite directed edges \(u\to v\) and \(v\to u\) appear simultaneously.

The answer can be huge so you only need to output it modulo \(p\).

Observation and Reformulation:

Since every vertex has out–degree 2, one way to form such a graph is to independently choose, for each vertex, two distinct targets from the other \(n-1\) vertices. This gives \(\Bigl(\binom{n-1}{2}\Bigr)^n\) choices. However, not all these choices lead to each vertex having in–degree 2. In fact, the valid graphs are exactly those for which the chosen edges (a total of \(2n\) edges) form a 0–1 matrix \(A=[a_{ij}]\) with zeros on the diagonal and each row and column summing to 2.

An alternative view is to notice that any such graph can be decomposed into the union of two disjoint permutation–matrices (with no fixed points). In other words, if we denote by \(!n\) the number of derangements (permutations without fixed points) of \(n\) elements, then every valid graph corresponds (in a 2–to–1 fashion) to a pair of derangements \((\sigma,\tau)\) satisfying \[ \tau(i)\neq\sigma(i)\quad \text{for every } i=1,2,\dots,n. \] Thus the answer is \[ \frac{1}{2}\,\Bigl|\{(\sigma,\tau):\,\sigma\hbox{ and }\tau\hbox{ are derangements of }[n],\, \tau(i)\neq \sigma(i)\,\forall i\}\Bigr| \pmod{p}. \]

Note: Because of the complexity of a closed–form solution, it is assumed that \(n\) is small (for example, \(n\le 8\)). A brute–force generation of all derangements and then counting the pairs that are disjoint (i.e. they never choose the same target for the same vertex) is acceptable.

inputFormat

The input consists of two space–separated integers \(n\) and \(p\) on a single line:

1. \(n\) — the number of vertices.
2. \(p\) — a prime number to take the answer modulo \(p\).

outputFormat

Output a single integer: the number of labeled directed simple graphs satisfying the degree conditions, taken modulo \(p\).

sample

3 1000000007

1