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