7591: BZOJ3591：最长上升子序列

给出1~n的一个排列的一个最长上升子序列，求原排列可能的种类数。

输入格式

第一行一个整数n。 第二行一个整数k，表示最长上升子序列的长度。 第三行k个整数，表示这个最长上升子序列。

输出格式

  第一行一个整数，表示原排列可能的种类数。

样例输入

5
3
1 3 4

样例输出

11

提示

【样例说明】
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)。
【数据规模和约定】
对于30%的数据，1 <= n <= 11。
对于70%的数据，1 <= n <= 14。
对于100%的数据，1 <= n <= 15，答案小于2^31。

题目来源

2014年国家集训队十五人互测 By strongoier