#5462. 「ROI 2012 Day 2」汗国军队

题目描述

译自 $ROI$ $2012$ $Day2$ $T4.$ Ордынское войско

在准备战斗时，汗王吉雷将他的军队中所有战士编号为从 $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

输入

5
3
1 3 4

输出

11

在第一个样例中，军队由五名战士组成。突击分队必须由编号为 $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)$。

样例 2

输入

3
3
1 2 3

输出

1

样例 3

输入

1
1
1

输出

1

数据范围与提示

详细子任务附加限制及分值如下表所示：

子任务	分值	附加限制
1	$40$	$1 \leq N \leq 8$
2	$10$	$9 \leq N \leq 10$
3		$N = 11$
4		$N = 12$
5		$N = 13$
6		$N = 14$
7		$N = 15$