题目描述

给定 $n,m$ 和长为 $m$ 的的序列 $a$，求有多少长为 $n$ 的排列 $p$ 满足 $a$ 恰好是 $p$ 的某一个最长上升子序列。

输入格式

第一行两个正整数 $n,m$。

第二行 $m$ 个正整数 $a_1,a_2,\cdots,a_m$。保证 $1 \le a_1 < \cdots < a_m \le n$。

输出格式

输出一行一个非负整数表示答案。

样例 $1$ 输入

4 2
2 4

样例 $1$ 输出

5

样例 $1$ 解释

符合条件的排列 $p$ 有：

2 1 4 3
2 4 1 3
2 4 3 1
3 2 1 4
3 2 4 1

样例 $2$ 输入

8 3
2 4 8

样例 $2$ 输出

873

样例 $3$ 输入

19 9
1 4 6 7 9 10 13 14 16

样例 $3$ 输出

107505523358

数据范围与提示

对于所有数据，$1\le m\le n\le 21$，$1\le a_i\le n$ 且 $a_i$ 严格单调递增。