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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor