题目描述

求有多少个排列 $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$ 取模的值。

5 2
1 3

5

数据范围

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