# Balance beam (2) P45300

Statement

html

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