Ebru wants to create a new language. They create every word from their alphabet consisting of \(\mathbf{M}\) symbols and each word contains at least 1 letter. Also for ease of use, they limit the length of every word to be at most \(\mathbf{N}\).

But Ebru's language has some rules. Every symbol \(\mathbf{i}\) in the alphabet has a limit of consecutive occurrences \(\mathbf{A_i}\). Which means if symbol \(\mathbf{i}\) = a has a value \(\mathbf{A_i} = 2\), it cannot repeat consecutively, meaning that a word can include a or aa but cannot include aaa.

Ebru wonders how many words are there in their new language. Can you help them find out?

Input

First-line consists of two space-separated integers \(\mathbf{N}\) and \(\mathbf{M}\), the upper limit for word length and number of symbols in the alphabet respectively.

Next \(\mathbf{M}\) lines have values of \(\mathbf{A_i}\), where each \(\mathbf{A_i}\) is the upper limit of consecutive occurrence for \(\mathbf{i}\)th symbol.

Batch #1:

• \(1 \leq \mathbf{N}, \mathbf{M} \leq 100\)
• \(1 \leq \mathbf{A_i} \leq \mathbf{N}\)

Batch #2:

• \(1 \leq \mathbf{N}, \mathbf{M} \leq 500\)
• \(1 \leq \mathbf{A_i} \leq \mathbf{N}\)

Output

Count of words in the language. Since this count can be huge, you need to take the modulo \(10^9+7\) before printing it.

Examples

Input:

3 3
1
2
3

Output:

32

Input:

5 2
1
2

Output:

21

Explanation

1st Input

Let's say the symbols are a, b and c respectively:

• a can consecutively occur at most 1,
• b can consecutively occur at most 2,
• c can consecutively occur at most 3 times.

In this case, number of words of length 1 is 1. (a, b, c)

Number of words of length 2 is 8. (ab, ac, ba, bb, bc, ca, cb, cc)

Number of words of length 3 is 21. (aba, abb, abc, bab, ...)

2nd Input

Let's say the symbols are a, b and c respectively:

• a can consecutively occur at most 1,
• b can consecutively occur at most 2 times.

In this case, number of words of length 1 is 1. (a, b)

Number of words of length 2 is 3. (ab, ba, bb)

Number of words of length 3 is 4. (aba, abb, bab, bba)

Number of words of length 4 is 5. (abab, abba, babb, baba, bbab)

Number of words of length 5 is 7. (ababa, ababb, abbab, babab, babba, bbaba, bbabb)