Counting 2‐Regular Directed Graphs

Given n labeled nodes (numbered from 1 to n), count the number of labeled directed simple graphs satisfying the following condition for every vertex \( i \):

$$\operatorname{deg_{out}}(i)=\operatorname{deg_{in}}(i)=2.$$

Self‐loops are not allowed (i.e. an edge from a node to itself cannot appear), but simultaneously having both edges \( u\to v \) and \( v\to u \) is permitted.

You only need to output the answer modulo a given prime number \( p \).

Note: In constructing the graph, each vertex’s two outgoing edges are chosen from the set of all other vertices (i.e. excluding itself), and the final graph must also have each vertex receiving exactly two incoming edges.

inputFormat

The input consists of a single line with two integers n and p, where n is the number of nodes and p is a prime modulus.

Constraints: n is small (e.g. n ≤ 10) so that a backtracking dynamic programming solution is feasible.

Example Input:
3 1000003

outputFormat

Output a single integer: the number of labeled directed simple graphs that satisfy the given degree conditions, taken modulo p.

Example Output:
1

sample

3 1000003

1