#2750. 魔法的碰撞

魔法的碰撞

Description

魔法总是令战斗的局面变幻莫测。然而魔力的碰撞则更是天马行空,甚至会出现无法控制而自取灭亡的情况。因此

,魔力碰撞总是没有办法的办法。不过在战场上大家可不会想太多了:看到敌人,直接一阵法术秒杀之,规则神马

的都是浮云了。因此,必须布阵时就避免可能的魔力碰撞。设想有一条长度为L的战线,你可以把你的魔法师们安

排在战线上的每个格子。每一个魔法师都有一个攻击范围di,排兵时必须保证任意两个魔法师的攻击范围的较大值

小于等于它们之间的距离(距离即为它们坐标的差值)。为了更好地迷惑敌人,你须要求出总共有多少种布阵的方

案。

Format

Input

第一行两个整数L,n,n代表魔法师个数。

第二行n个数,描述魔法师的攻击范围di。

N≤40,di≤40,L≤1000000

Output

一行,一个整数,代表方案数mod 1000000007的值。

Samples

9 3
1 2 4
42