题目描述

对于一个 $1-n$ 的排列 ${p_1,p_2,...,p_n}$，将 $p_i$ 和 $p_j$ 交换，需要的代价为 $2\times |i-j|-1$，记 $f(p)$ 表示通过交换将排列 $p$ 变成从小到大的排列，即 ${1,2,3…,n}$ 的最小代价。一个愚蠢的算法是用 $g(p)=\sum max(0,i-pi)$ 来估算 $f(p)$。给出 $1-n$ 的排列的前 $m$ 个元素，求有多少个排列 $p$ 满足条件 $f(p)=g(p)$。

输入格式

输入 $n$ 和 $m$，表示 $1-n$ 的排列，以及确定了前 $m$ 个数。

接下来一行包含 $m$ 个数，表示排列中确定的前 $m$ 个数。

输出格式

输出一行，表示有多少个排列满足条件，输出答案$\mod 10^9+7$。

3 0

5 2 1 4

5

3

数据规模与约定

对于 $100\%$ 的数据，$n\le 2000,m\le n$