Counting Spanning DAGs

Recently, Little C learned about topological sorting. A topological ordering of a directed acyclic graph (DAG) \(G\) is a linear ordering of all vertices such that for every directed edge \((u,v)\) in \(G\), vertex \(u\) comes before \(v\) in the ordering. For example, if \(G\) has vertices \(\{1,2,3,4\}\) and edges \(\{(1,2),(1,3),(2,4),(3,4)\}\), then both \((1,2,3,4)\) and \((1,3,2,4)\) are valid topological orders.

Little C performed a topological sort on a simple (i.e. with no multiple edges) DAG and recorded the resulting ordering (which we fix as \(1,2,\dots,n\)). Unfortunately, he lost the original graph. Besides the topological order, he only remembers that the original graph contained exactly \(k\) edges, and there exists a vertex \(u\) in the graph which can reach all other vertices. Notice that in any DAG with a fixed topological order, if there exists a vertex that can reach every other vertex, it must be the first vertex in the ordering.

Your task is to count the number of simple DAGs on \(n\) vertices (with vertices ordered as \(1,2,\dots,n\)) having exactly \(k\) edges and satisfying the property that vertex 1 can reach every other vertex. Since the answer may be very large, output the answer modulo \(m\).

The DAG is constructed as follows: for every vertex \(i\) from 2 to \(n\), you independently choose a nonempty subset of vertices from \(\{1,2,\dots,i-1\}\) to be connected to \(i\) by a directed edge. The total number of edges of the graph is the sum, over \(i=2\) to \(n\), of the sizes of the chosen subsets. Count the number of ways to make these choices such that the total number of edges is exactly \(k\).

Input Format: A single line containing three integers \(n, k, m\).

Output Format: A single integer representing the number of valid DAGs modulo \(m\).

inputFormat

The input consists of a single line with three positive integers:

• n — the number of vertices. The vertices are labeled \(1,2,\dots,n\) in the fixed topological order.
• k — the exact number of edges in the graph.
• m — the modulus.

It is guaranteed that \(1 \le n \le 100\) and \(0 \le k \le \frac{n(n-1)}{2}\).

outputFormat

Output a single integer: the number of simple DAGs satisfying the conditions, taken modulo \(m\).

sample

2 1 100

1