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**)