非奈特

题目描述

求有多少个排列 $a$，使得其长度为 $m$ 的前缀是给定的序列 $b$，且：

$$\sum_{i=1}^n \max(0, i - a_i) = \sum_{i=1}^n \sum_{j=i+1}^n [a_i > a_j]$$

答案向 $10^9+7$ 取模。

输入格式

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

接下来一行 $m$ 个整数，表示序列 $b$。

输出格式

一行一个整数，表示答案对 $10^9 + 7$ 取模的值。

数据范围

• 对于 $30\%$ 的数据，$n,m \leq 10$
• 对于 $60\%$ 的数据，$n,m \leq 10^3$
• 对于 $100\%$ 的数据，$1 \leq n,m \leq 2 \times 10^5$

样例数据 1

输入

5 2
1 3

输出

5