We’re preparing your current view and syncing the latest data.
Given three integers n, k, and a sequence of k positive integers, count the number of ways to write n as a sum of the given integers where order matters. Since the answer can be large, output it modulo 10^9+7.
The first line contains two integers n and k (1 ≤ n, k ≤ 1000). The second line contains k integers representing the allowed positive integers.
Output the number of ways modulo 10^9+7.
1 ≤ n, k ≤ 1000. Each number in the sequence is a positive integer not exceeding n.
Example 1
Input
3 2 1 2
Output
3
Explanation
The ways to write 3 are: 1+1+1, 1+2, and 2+1.