P15301 [ROI 2012 Day 2] army Khanate Army

Translation source: [loj #5462. "ROI 2012 Day 2" Khanate Army](https://loj.ac/p/5462).

When preparing for battle, Khan Girey numbered all warriors in his army with natural numbers from $1$ to $N$. Since the warriors are good at fighting but not at counting, no matter how they line up in a row, they will stand in an arbitrary order. We call one or more warriors standing in a row a **squad**. If the warriors' numbers in the queue form a strictly increasing sequence, then the squad is called **correct**. Among all correct squads, Khan Girey chooses those with the largest number of warriors as **assault squads**. For example, in the queue of four warriors $1\ 3\ 2\ 4$, the assault squads are $1\ 3\ 4$ and $1\ 2\ 4$, while the squad $1\ 4$ is correct but not an assault squad. Some warriors are Khan Girey's personal guards. You need to write a program to compute how many different queue permutations make the Khan's guards form an assault squad.

The first line of the input file contains a natural number $N$ $(1 \leq N \leq 15)$, the total number of warriors. The second line contains a natural number $K$ $(1 \leq K \leq N)$, the number of the Khan's guards. The third line contains $K$ distinct natural numbers (not exceeding $N$), given in increasing order, representing the numbers of the Khan's guards. The numbers are separated by spaces.

The output file should contain one integer, the number of different ways to arrange all warriors in a queue such that, in each arrangement, the Khan's guards form an assault squad.

In the first sample, the army consists of five warriors. The assault squad must consist of the three warriors numbered $1, 3, 4$. There are $11$ queues that satisfy this condition: $(1, 3, 2, 5, 4)$, $(1, 3, 5, 2, 4)$, $(1, 3, 5, 4, 2)$, $(1, 5, 3, 2, 4)$, $(1, 5, 3, 4, 2)$, $(2, 1, 3, 5, 4)$, $(2, 1, 5, 3, 4)$, $(2, 5, 1, 3, 4)$, $(5, 1, 3, 2, 4)$, $(5, 1, 3, 4, 2)$, $(5, 2, 1, 3, 4)$. The detailed additional constraints and scores for subtasks are as follows: | Subtask | Score | Additional Constraints | | :-----: | :---: | :--------------------: | | $1$ | $40$ | $1 \leq N \leq 8$ | | $2$ | $10$ | $9 \leq N \leq 10$ | | $3$ | $10$ | $N = 11$ | | $4$ | $10$ | $N = 12$ | | $5$ | $10$ | $N = 13$ | | $6$ | $10$ | $N = 14$ | | $7$ | $10$ | $N = 15$ | Translated by ChatGPT 5