A vault keypad advances a bolt along n positions. On each press the bolt moves forward by one of k allowed step sizes (the allowed sizes are given and are distinct positive integers). Two unlock sequences are different if the ordered list of step sizes used differs.
Count the number of distinct sequences of presses whose step sizes sum to exactly n (moving the bolt from position 0 to position n). Print the count modulo 1000000007.
Input format
Line 1: two integers n and k.
Line 2: k space-separated distinct positive integers, the allowed step sizes.
Output format
A single integer: the number of ordered sequences summing to n, taken modulo 1000000007.
Constraints
- 0 <= n <= 40
- 1 <= k <= 6
- Each allowed step size is between 1 and 40, and all k sizes are distinct.
- The empty sequence is the only way to reach position 0, so the answer for n = 0 is 1.