Answer的排队

时间限制:10s      空间限制:256MB

题目描述

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。


题目来源

没有写明来源

Menuappsclose