题目描述

在提瓦特大陆，故事总是与神秘融合。神里绫华，这位稻妻的贵族，不仅以其冰花之舞著称，还因她对古老秘密的追寻而闻名。一天，她在稻妻的一座隐秘图书馆深处偶然发现了一本泛黄的古书，书中记载着一种被称作“转折排列”的神奇序列。这些序列据说是开启通往遗忘之地宝藏的钥匙，每一个数字都是一步向着古代智慧和力量的道路。

“转折排列”是一种独特的数列，它从 $1$ 数到 $n$ ，每个数字在这个序列中唯一出现。对于一个给定的排列 $p_1,p_2,…,p_n$ ，定义qi为数字i在序列中的位置，即 $p_{q_i}=i$。只有当所有的$i=2,3,…,n-1$ 满足一个神秘条件 $(q_i-q_{i-1})(q_i-q_{i+1})>0$ 时，这个序列才能被称作“转折排列”，它们像是在数列中舞动，优雅地转折。

神里绫华，这位对遗失的知识充满渴望的贵族，立志要追寻这些“转折排列”的秘密。她相信，这些序列不仅是数学上的挑战，更是一条通往过去的道路，一个揭示隐藏在提瓦特大陆深处未知宝藏和力量的机会。

在她的探索中，神里绫华遇到了一个挑战。她只能获取到一个“转折排列”的前 $k$ 个数字的线索，而现在她需要找出所有可能的完整“转折排列”有多少种。每一种可能不仅是对她智慧的考验，也是一步接近那些古老力量的机会。但在这个探索中，计算的复杂性远超她预期，因此她需要将答案对 $1000000007$ 取模，以保持计算的可行性。

随着神里绫华深入这个挑战，她知道，每一个正确的排列都是解开大陆深处秘密的关键。她的冒险不仅是对过去的探寻，也是一场对自己能力的考验。现在，加入神里绫华的探索，帮助她计算出对于这个不完整的“转折排列”，有多少种可能的完整排列满足要求,如果给定的不完整的“转折排列”不合法，请输出 $0$。

输入格式

第一行包含三个整数 $n,k$, 含义如题。

第二行包含 $k$ 个整数，表示 $p$ 排列的前 $k$ 项，保证均为小于 $n$ 的正整数，且互不相同

输出格式

仅一个正整数，表示可能的合法序列数量

样例

5 5
1 2 3 4 5

0

5 2
2 4

6

5 2
1 3

3

20 5
3 9 7 15 5

623772083

10 0

101042

10 3
3 7 9

840

样例解释 2

六种排列分别是 [2 4 3 1 5] [2 4 3 5 1] [2 4 5 1 3] [2 4 1 3 5] [2 4 5 3 1] [2 4 1 5 3]

数据规模与约定

保证 $1\le k \le n \le 500$