题目描述

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

输入格式

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

输出格式

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

5
3
1 3 4

11

数据规模与约定

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

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

样例说明

$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)$。

题目来源

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