题目描述

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

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

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

形式化地，第 $i(2\le i\le n)$ 次操作无效，当且仅当 $pi>\mathop{\max}\limits{j=1}^{i-1}\min(pj,p{j+1})$。

现给定 $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$ 的结果或无解。

样例

input

3 0

output

4

数据范围与提示

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