P15301 [ROI 2012 Day 2] army 汗国军队

翻译来源：[loj #5462. 「ROI 2012 Day 2」汗国军队](https://loj.ac/p/5462)。

在准备战斗时，汗王吉雷将他的军队中所有战士编号为从 $1$ 到 $N$ 的自然数。由于战士们擅长战斗而不擅长计数，无论如何排列成一排，他们都会以任意顺序站立。 我们将站在一排中的一个或多个战士称为**分队**。如果这些战士在队列中的编号形成一个递增的数字序列，则称该分队为**正确的**。在所有正确的分队中，汗王吉雷选择人数最多的作为**突击分队**。例如，在由四名战士组成的队列 $1\ 3\ 2\ 4$ 中，突击分队是 $1\ 3\ 4$ 和 $1\ 2\ 4$，而分队 $1\ 4$ 是正确的，但不是突击分队。 某些战士是汗王吉雷的贴身护卫。 你需要编写一个程序，计算有多少种队列排列方式，使得汗王的护卫构成突击分队。

输入文件的第一行包含一个自然数 $N$ $(1 \leq N \leq 15)$，表示战士的总人数。 第二行包含一个自然数 $K$ $(1 \leq K \leq N)$，表示汗王护卫的数量。 第三行包含 $K$ 个不同的自然数（不超过 $N$），以升序排列，表示汗王护卫的编号，数字之间以空格分隔。

输出文件应包含一个整数，表示所有战士排列成队列的不同方式数量，使得汗王的护卫在每种排列中都构成突击分队。

在第一个样例中，军队由五名战士组成。突击分队必须由编号为 $1, 3, 4$ 的三名战士组成。满足这一条件的队列有 $11$ 种：$(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)$。 详细子任务附加限制及分值如下表所示： | 子任务 | 分值 | 附加限制 | | :----: | :--: | :---------------: | | $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$ |