#4133. Answer的排队

内存限制:256 MiB 时间限制:10 Sec

题目描述

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

输入格式

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

输出格式

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

样例

样例输入


			
4 3
1 3 4

样例输出


			
3

数据范围与提示

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