Given a natural number *x* and *n* different coin values *c*_{1} … *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} … *c*_{n}.
Assume 1 ≤ *n* ≤ 1000,
1 ≤ *c*_{i} ≤ *x* ≤ 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.

Public test cases

**Input**

4 2 1 2 400 1 200 400 1 300 5 3 4 2 1 5 5 1 2 3 4 5 120 29 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

**Output**

3 1 0 6 14 36982290

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Albert Atserias
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++