You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

辰辰非常喜欢数列，尤其是排列，因此辰辰对排列有自己独特的品味。对于长度为 $n$ 的排列 $A_1, A_2, \cdots, A_n$，若 $\forall 1\le i\le n, A_{A_i}=i$，辰辰就认为这样的排列符合自己的品味。

辰辰于是想出了一个有关排列的问题，对于长度为 $k$ 的排列 $B_1, B_2, \cdots, B_k$，有多少符合辰辰品味的长度为 $n$ 的排列，使得 B 是它的子序列？

输入格式

第一行两个正整数 $n, k$，含义如题所示。

第二行 $k$ 个正整数，表示排列 $B$。

输出格式

一行一个整数表示答案。

样例

样例输入 1

5 3
3 1 2

样例输出 1

3

样例输入 2

20 10
4 8 7 9 10 1 3 5 2 6

样例输出 1

9233

数据范围

• 对于 $10 \%$ 的数据，$n \leq 10$。
• 对于 $30 \%$ 的数据，$n \leq 40$。
• 对于 $60 \%$ 的数据，$n \leq 100$。
• 对于 $100 \%$ 的数据，$1 \leq k \leq n \leq 200$，$B$ 是一个 $1 \ldots k$ 的排列。