Patriotic Painting 2

You are given a strip $1\times n$, consisting of $n$ yellow cells.

You will do $k$ operations with this strip. In the $i$-th operation, you must select some exactly $a_i$ consecutive cells of this strip, and paint all of them blue (if the cell was yellow, it will turn blue, and if it was blue, it will remain blue).

How many different colorings of the strip can you get? Since this number can be very large, print it modulo $10^9+7$.

Two colorings of the strip are considered different if some cell is painted yellow in one of them and blue in the other one.

Input

The first line contains two integers $n,k$ ($1\le n\le 10^9,1\le k\le 4$).

The second line contains $k$ integers $a_1,\dots ,a_k$ ($1\le a_i\le n$).

Output

Output the number of different colorings of the strip that you can get modulo $10^9+7$.

Examples