Barra d'equilibris (2) P45300

Statement

Una gimnasta es troba al punt mig d’una barra d’equilibris de longitud $m$ . La gimnasta ha de fer $n$ salts endavant o enrera, cadascun de longitud $\ell_i$ , sense sortir-se mai de la barra. Feu un programa que calculi de quantes maneres es pot acabar l’exercici a cada posició. Els salts s’han de fer tots, i en l’ordre donat.

Entrada

L’entrada consisteix en la longitud $m$ , seguida del nombre $n$ , seguit de les longituds $\ell_1, \dots, \ell_n$ dels salts. Suposeu $2 \le m \le 10^3$ , que $m$ és parell, $0 \le n \le 10^4$ , i $1 \le \ell_i \le 100$ .

Sortida

Suposant que la posició inicial és 0 (per tant, les posicions vàlides estan a $[-m/2, m/2]$ ), escriviu en ordre les posicions on es pot acabar, junt amb el nombre de maneres de fer-ho mòdul $10^8 + 7$ .

Public test cases

Input

1000 3
100 10 1

Output

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

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: Catalan
Other languages: English
Official solutions: C++
User solutions: C++