Counted Arrays

An array \(a\) of length \(n\) is called counted if and only if there exists a way to partition it into one or more contiguous subarrays such that for every subarray, the minimum element equals the length of that subarray. Formally, there exist indices \(0 = x_1 < x_2 < \cdots < x_m = n\) such that for every \(1 \le i < m\):

[ \min_{j=x_i+1}^{x_{i+1}} a_j = x_{i+1} - x_i, ]

You are given a positive integer set \(S\). Count the number of arrays \(a\) of length \(n\) that satisfy \(a_i \in S\) for all \(1 \le i \le n\) and that are counted. Since the answer can be large, output it modulo \(10^9+7\).

inputFormat

The first line of input contains two integers \(n\) and \(k\) where \(n\) is the length of the array and \(k\) is the size of the set \(S\).

The second line contains \(k\) distinct positive integers representing the set \(S\).

outputFormat

Output a single integer: the count of counted arrays modulo \(10^9+7\).

sample

3 2
1 2

3