8498: BZOJ4498：魔法的碰撞

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

输入格式

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

输出格式

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

样例输入

9 3
1 2 4

样例输出

42

提示

没有写明提示

题目来源

没有写明来源