There are M people living in an island. They all wish to go to heaven. One day a magical stair appears in the island which is a path to heaven. Each person i has some power ki which indicates the maximum amount of steps that person can jump. There are N steps in the magical stair. Initially all the people are standing at ground and it takes 1 second for a person to make a jump within his capacity. A person reaches heaven when he reaches the Nth stair. Note that a person can only jump upward. You have to calculate the number of ways in which all the people reach the heaven at the same time.
Input :
First line contains two integers N and M, which denotes the number of steps and the number of people respectively. Next line contains M integers which denotes the power of each people.
Output :
Print a single integer which denotes the number of ways in which all people reach heaven at the same time. Since the output may be very large output it modulo 109 + 7.
Constraints :
1 <= N <= 300
1 <= M <= 105
1 <= ki <= N
The 5 ways are (0 -> 1 -> 3, 0 -> 1 -> 3), (0 -> 1 -> 3, 0 -> 2 -> 3), (0 -> 2 -> 3, 0 -> 1 -> 3), (0 -> 2 -> 3, 0 -> 2 -> 3), (0 -> 1 -> 2 -> 3, 0 -> 1 -> 2 -> 3). In the first 4 ways both of them reach the heaven at time 2sec and in the last way they reach at 3sec.
