You climb a staircase of n stairs. You are given a set of m distinct allowed stride lengths. Each move you take goes up by one of the allowed stride lengths. Count the number of ordered sequences of moves whose lengths add up to exactly n (two sequences that use the same multiset of strides in a different order are counted separately).
Report the count modulo 1000000007. Climbing 0 stairs has exactly one sequence: the empty one.
Input format
Line 1: two integers n and m.
Line 2: m space-separated distinct positive integers, the allowed stride lengths.
Output format
A single integer: the number of ordered stride sequences summing to n, modulo 1000000007.
Constraints
- 0 <= n <= 100000
- 1 <= m <= 10
- 1 <= each stride length <= 50, all distinct