Two coins of each kind (2) P52074

Given a natural number $x$ and $n$ different coin values $c_1 \ldots c_n$, compute in how many ways it is possible to achieve change $x$ by using each value at most twice. Here, two coins with the same value are considered different.

For example, if $x = 4$ and the available values are $1$ and $2$, then there are three ways to achieve it: $1 + 1' + 2$, $1 + 1' + 2'$, and also $2 + 2'$.

Input

Input consists of several cases. Every case begins with $x$ and $n$, followed by $c_1 \ldots c_n$. Assume $1 \le n \le 1000$, $1 \le c_i \le x \le 1000$, and that all $c_i$ are different.

Output

For every case, print the number of ways to exactly achieve change $x$ by using each value at most twice. Since the result can be huge, make the computations modulo $10^8 + 7$.