Balance beam (2) P45300


Statement
 

pdf   zip

thehtml

A gymnast is at the midpoint of a balance beam of length m. The gymnast must jump n times forward or backward, never leaving the bar. The i-th jump has length ℓi. Write a program to computes in how many ways the gymnast can finish the exercise at every position. The gymnast cannot skip any jump, nor change the order of the jumps.

Input

Input consist of the length m, the number n, and the lengths ℓ1, …, ℓn. Assume 2 ≤ m ≤ 103, that m is even, 0 ≤ n ≤ 104, and 1 ≤ ℓi ≤ 100.

Output

Assuming that the initial position is 0 (hence, the valid positions belong to [−m/2, m/2]), print in order the positions where the gymnast can finish, together with the number of ways modulo 108 + 7.

Public test cases
  • Input

    1000 3
    100 10 1
    

    Output

    -111 1
    -109 1
    -91 1
    -89 1
    89 1
    91 1
    109 1
    111 1
    
  • Input

    40 2
    10 10
    

    Output

    -20 1
    0 2
    20 1
    
  • Input

    1000 0
    

    Output

    0 1
    
  • Input

    10 1
    100
    

    Output

    
            
                                
  • Input

    30 4
    5 1 20 2
    

    Output

    -12 1
    12 1
    
  • Input

    6 5
    1 1 1 1 1
    

    Output

    -3 4
    -1 10
    1 10
    3 4
    
  • Input

    100 36
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    

    Output

    -36 1
    -34 36
    -32 630
    -30 7140
    -28 58905
    -26 376992
    -24 1947792
    -22 8347680
    -20 30260340
    -18 94143280
    -16 54186842
    -14 805254
    -12 51677616
    -10 10789439
    -8 96296941
    -6 67902175
    -4 7871599
    -2 97496005
    0 75134670
    2 97496005
    4 7871599
    6 67902175
    8 96296941
    10 10789439
    12 51677616
    14 805254
    16 54186842
    18 94143280
    20 30260340
    22 8347680
    24 1947792
    26 376992
    28 58905
    30 7140
    32 630
    34 36
    36 1
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++