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 k_i 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 N^th 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 10⁹ + 7.

Constraints : 

1 <= N <= 300

1 <= M <= 10⁵

1 <= k_i  <= N