题目描述
对一个长度为 n 的数组进行 n 次操作,每次将 1 到 pi 赋值。
由于蒟蒻非常鶸,所以在第 2 到 n 次操作之前,他只会将 1 到 min(pi−1,pi) 初始化。
如果不是第一次的某个操作将一个未初始化的变量赋值,则该操作为无效操作。第一次操作不需要初始化。
形式化地,第 i(2≤i≤n) 次操作无效,当且仅当 pi>j=1maxi−1min(pj,pj+1)。
现给定 n,m 和 p1,p2,…,pm。
求对于所有满足条件的排列 p(共有 (n−m)! 种)中,蒟蒻没有无效操作的种数。
若没有满足条件的方案则输出 -1
。注意,是 −1,不是 0!
否则,你只要回答答案 mod109+7 的结果即可。
输入格式
第一行两个整数 n,m;
第二行 m 个整数 第 i 个数为 pi。
输出格式
一个正整数或 -1
,表示满足题意的方案数 mod109+7 的结果或无解。
样例
3 0
4
数据范围与提示
n≤1018,m≤1000000,n≥m
pi 互不重复且小于等于 n