Two coins of each kind (2) P52074

Given a natural number x and n different coin values c₁ … 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₁ … 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⁸ + 7.