UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4133. Answer的排队

统计 下载数据

Description

Answer有N个朋友, 每个朋友有一个身高值, 没有两个朋友身高相同。 现在,Answer要给他的朋友们排队成一排,他希望队伍美观,于是给定了一个有 N 个元素的数组 a,满足 1=a1<a2<a3…<am=N ,表示他希望排在 a1-a2 位置的朋友身高递增,a2-a3位置的朋友身高递减……依次类推。
Answer希望知道有多少种排队方式满足要求,由于方案数可能很大,所以只需输出答案模1000000007后的值。

Input

输入的第一行包含两个正整数N,M,
第二行包含M个数,表示ai。

Output

输出一个整数,表示方案数模1000000007后的值。

Sample Input

4 3
1 3 4

Sample Output

3

Hint

对于100%的数据,满足n ≤ 20000,m ≤ 25。


Source