Patriotic Painting 2#10823
You are given a strip 1 \times n, consisting of yellow cells.
You will do operations with this strip. In the -th operation, you must select some exactly a_i consecutive cells of this strip, and paint all of them blue (if the cell was yellow, it will turn blue, and if it was blue, it will remain blue).
How many different colorings of the strip can you get? Since this number can be very large, print it modulo 10^9+7.
Two colorings of the strip are considered different if some cell is painted yellow in one of them and blue in the other one.
The first line contains two integers (1 \le n \le 10^9, 1 \le k \le 4).
The second line contains integers a_1, \ldots ,a_k (1 \le a_i \le n).
Output the number of different colorings of the strip that you can get modulo 10^9+7.
Example 1
Example 2
Example 3