408174: GYM103037 E Algo's Rhythm

Algo the serial composer absolutely loves to write music and does it all the time. In fact, he has composed so many pieces over the years that now he has grown bored of having so much creative freedom and would like to give himself a challenge. Algo will now limit himself to composing with only the notes from a set of $$$N$$$ chosen note lengths, and he wants to match the overall target length of his song exactly.

For instance, if Algo wants to compose a 1-measure song using only quarter notes, half notes, and whole notes—of beat-lengths 1, 2, and 4 respectively—then there are 6 total possible songs that he could compose:

Algo has just been commissioned to write a song that is $$$M$$$ four-beat measures long. Determine how many unique songs ending at exactly $$$M$$$ measures Algo could possibly write, using only his $$$N$$$ chosen notes!

The first line of input contains two integers $$$M$$$ and $$$N$$$, where $$$M$$$ ($$$1 \leq M \leq 10^5$$$) is Algo's desired song length in 4-beat measures and $$$N$$$ ($$$1 \leq N \leq 20$$$) is the number of unique note lengths that Algo will limit himself to using. Then, the second line of input contains $$$N$$$ space-separated integers, where each integer $$$n_i$$$ ($$$1 \leq n_i \leq M*4$$$) represents a chosen note length in beats.

Output the total number of $$$M$$$-measure songs that Algo could possibly compose from his chosen notes! Because this amount could be very large, output the number of songs modulo $$$10^9+7$$$.

1 3
1 2 4

6

5 2
3 6

0