AT_nyc2015_13.お絵かき

すぬけ君决定画画。他首先准备了一张细长的白纸，并将其分成 $1 \times N$ 的格子。接下来，すぬけ君将进行 $K$ 次操作。在第 $i$ 次操作中，他会选择连续的 $a_i$ 个格子，并将它们全部涂黑。在这个操作中，被选中的格子中原本是白色的会变成黑色，原本就是黑色的则保持不变。

请你求出すぬけ君可以画出多少种不同的画作，结果对 $1,000,000,007$ 取模。如果最终某些格子的颜色不同，则认为是不同的画作。即使旋转后相同，也认为是不同的画作。

输入包含两行。

第一行包含两个整数 $N$ 和 $K$。

接下来的 $K$ 行，每行包含一个整数 $a_i$。

输出一个整数，表示すぬけ君可以画出的不同画作的数量，对 $1,000,000,007$ 取模。

数据范围

• $1 \leq N \leq 10^9$
• $1 \leq K \leq 4$
• $1 \leq a_i \leq N$

由 ChatGPT 4.1 翻译