A bot starts at tile 0 on an infinite strip of tiles numbered 0, 1, 2, .... In one hop it moves forward by one of k allowed step lengths (each may be reused any number of times, in any order). Count the number of distinct ORDERED hop sequences that land the bot exactly on tile n (two sequences are distinct if they differ in the step length used at some hop, or in the number of hops). Since this count can be large, print it modulo 1000000007.
Input format
Line 1: two integers n k.
Line 2: k distinct space-separated positive integers, the allowed step lengths.
Output format
A single integer: the number of ordered hop sequences landing exactly on tile n, modulo 1000000007. (If n = 0, the empty sequence counts, so the answer is 1.)
Constraints
- 0 ≤ n ≤ 5000
- 1 ≤ k ≤ 8
- 1 ≤ each step length ≤ 20