409724: GYM103708 F Froginald the frog

Froginald is a very happy frog living in his pond, he got very excited when he knew that the Grand Prix of Mexico is starting again so he decided to go immediately to participate! Even if that means missing an exam, a class, or a day of work.

The road for the Grand Prix is filled with rocks, rocks that we need to overcome to be closer and closer to the Grand Prix.

In the case of Froginald, he can simply jump over them, the road of rocks is a linear path to the Grand Prix, and Froginald can jump to +1 of his position or +2, always ending up closer to the goal. Unfortunate for Froginald some of the rocks are missing being that if he tries to jump to a place with a missing rock he would end up drowning in the lake, so he would definitely try to avoid that.

The road to the Grand Prix is long, and there are many ways to travel it, Froginald is so excited about starting his journey that he wants to know how many ways is for him to reach the goal!

Froginald starts in position 0 which will always have a rock, as well as position $$$N$$$.

The first line has two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10^9$$$) ($$$1 \leq M \leq 1000000$$$) indicating how long the road is, and how many holes are in the road. The next line will have $$$M$$$ integers indicating that the position $$$a_i$$$ doesn't have a rock.

A single integer that represents the number of ways that Froginald has to reach the position $$$N$$$, because this number can be very large print it modulo $$$10^9 + 7$$$.

5 1
2

2