已知某个 $1 \sim n$ 的全排列 的 最长上升子序列为 $a_i$ ，长度为 $k$。

求该全排列可能的方案数。

输入格式

第一行一个整数 $n$。

第二行一个整数 $k$。

第三行 $k$ 个整数 $a_i$。

输出格式

一行一个整数，表示答案。

样例输入

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\le n \le 11$。

对于70%的数据，$1 \le n \le 14$。

对于100%的数据，$1 \le n \le 15$，答案小于 $2^{31}$。