You have n-strip colorless bar code, where each strip is of unit length. You are given k brushes having their own different width. Using a brush of width w you can paint at a time exactly w consecutive strips on a bar code with black color, with the condition that initially all those w strips should be colorless. You can use any brush infinite times.

Find the number of distinct bar codes that you can create. Two bar codes are considered different if there exists at least one strip that is black in first and colorless in other. Print your answer modulo 10⁹+7.

Input:

First line of input contains two space separated integers n and k denoting number of strips on bar code and number of brushes respectively. Next line contains k space separated integers, the i^th integer denoting the width of i^th brush.

Output:

Output in single line, your answer modulo 10⁹+7.

Constraints:

1 ≤ n , k ≤ 10³
1 ≤ width of i^th brush (w_i) ≤ 10³