UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4498. 魔法的碰撞

Statistics 下载数据

Description

魔法总是令战斗的局面变幻莫测。然而魔力的碰撞则更是天马行空,甚至会出现无法控制而自取灭亡的情况。因此
,魔力碰撞总是没有办法的办法。不过在战场上大家可不会想太多了:看到敌人,直接一阵法术秒杀之,规则神马
的都是浮云了。因此,必须布阵时就避免可能的魔力碰撞。设想有一条长度为L的战线,你可以把你的魔法师们安
排在战线上的每个格子。每一个魔法师都有一个攻击范围di,排兵时必须保证任意两个魔法师的攻击范围的较大值
小于等于它们之间的距离(距离即为它们坐标的差值)。为了更好地迷惑敌人,你须要求出总共有多少种布阵的方
案。

Input

第一行两个整数L,n,n代表魔法师个数。
第二行n个数,描述魔法师的攻击范围di。
N≤40,di≤40,L≤1000000

Output

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

Sample Input

9 3
1 2 4

Sample Output

42

Hint

Source