Segments in a Regular Polygon

Dohyun marked $N$ points on a sheet of paper to form a regular $N$-gon. The vertices are numbered $1$ through $N$ clockwise.

He then drew $M-1$ segments. He connected the vertices $P_0, P_1, \dots, P_{M-1}$ in that order: $P_0$ to $P_1$, $P_1$ to $P_2$, and so on up to $P_{M-2}$ to $P_{M-1}$.

Now he wants to keep drawing so that every remaining vertex is visited exactly once and the drawing returns to $P_0$. If the remaining vertices are visited in the order $T_0, T_1, \dots, T_{N-M-1}$, he connects $P_{M-1}$ to $T_0$, $T_0$ to $T_1$, and so on up to $T_{N-M-2}$ to $T_{N-M-1}$, and finally $T_{N-M-1}$ to $P_0$. Every vertex that does not appear in $P$ appears in $T$ exactly once.

Every newly drawn segment must cross at least one segment that is already on the paper. The segments already on the paper include the ones drawn along $P$ and the ones drawn earlier in this process. Two segments cross when they share a point that lies in the interior of both, so two segments that share only an endpoint do not cross.

Given $N$, $M$, and $P$, write a program that counts the possible orders $T$.

The first line contains $N$ and $M$, separated by a space. ($4 \le N \le 18$, $2 \le M \le N-1$)

The second line contains the $M$ numbers $P_0$ through $P_{M-1}$ in order. Each number is between $1$ and $N$, and all of them are different.

Print the number of possible orders $T$ on the first line.