题目描述

对一个长度为 $n$ 的数组进行 $n$ 次操作，每次将 $1$ 到 $p_i$ 赋值。

由于蒟蒻非常鶸，所以在第 $2$ 到 $n$ 次操作之前，他只会将 $1$ 到 $\min(p_{i-1},p_i)$ 初始化。

如果不是第一次的某个操作将一个未初始化的变量赋值，则该操作为无效操作。第一次操作不需要初始化。

形式化地，第 $i$ $(2\le i\le n)$ 次操作无效，当且仅当

现给定 $n,m$ 和 $p_1,p_2,\ldots,p_m$。

求对于所有满足条件的排列 $p$（共有 $(n-m)!$ 种）中，蒟蒻没有无效操作的种数。

若没有满足条件的方案则输出 $-1$。注意，是 $-1$，不是 $0$！

否则，你只要回答答案 $\bmod 10^9+7$ 的结果即可。

输入格式

第一行两个整数 $n,m$；
第二行 $m$ 个整数，第 $i$ 个数为 $p_i$。

输出格式

一个正整数或 $-1$，表示满足题意的方案数 $\bmod 10^9+7$ 的结果或无解。

样例

输入

3 0

输出

4

数据范围与提示

$n \le 10^{18}$, $m \le 1000000$, $n \ge m$
$p_i$ 互不重复且小于等于 $n$。