Two coins of each kind (2) P52074


Statement
 

pdf   zip

thehtml

Given a natural number x and n different coin values c1cn, 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 c1cn. Assume 1 ≤ n ≤ 1000, 1 ≤ cix ≤ 1000, and that all ci 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 108 + 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++