A switchback trail is climbed with strides. There are k allowed stride lengths (distinct positive integers). A climb is an ordered sequence of strides whose lengths sum to exactly n, with one rule: you may never take the same stride length twice in a row (two consecutive strides must differ). Two climbs are different if the ordered sequence of stride lengths differs.
Count the number of valid climbs. Print the count modulo 1000000007. The empty climb (no strides) reaches n = 0 and is valid.
Input format
Line 1: two integers n and k.
Line 2: k space-separated distinct positive integers, the allowed stride lengths.
Output format
A single integer: the number of valid climbs, taken modulo 1000000007.
Constraints
- 0 <= n <= 18
- 1 <= k <= 5
- Each stride length is between 1 and 18, and all k lengths are distinct.