How many possibilities?

Time limit2sMemory limit1024 MB

Summary

Count the key press sequences on a staggered N by N keyboard where consecutive pressed keys are at the given distances, modulo 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Math, Geometry
Solved: No attempts yet

Problem

UFOs are steered with giant keyboards. Each keyboard has $N$ rows with $N$ keys in each row. Each row starts half a key further to the right than the row before it.

Two keys are neighbors if they touch along an edge. The distance between keys $A$ and $B$ is the minimum number of steps needed to get from $A$ to $B$ , where each step moves to a neighbor of the current key. In the figure, the distance between the keys and is 4.

A UFO war is underway. The enemy UFO has just started a complicated maneuver, and the pilot pressed $K + 1$ keys to perform it. To plan a counter-maneuver, it would help to know which keys were pressed. We only know the distance between the first and second pressed keys, the distance between the second and third, and so on. How many different key press sequences match this information?

Since the true answer may be huge, print it modulo $10^9 + 7$ .

Input

The first line of the file contains two integers $N$ and $K$ ( $2 \le N \le 300$ , $1 \le K \le 50$ ). The second line contains $K$ space-separated integers $A_1, A_2, \ldots, A_K$ ( $1 \le A_i < N$ ), where $A_i$ is the distance between the $i$ -th and $(i+1)$ -th pressed keys.

Output

Print one integer: the number of possible key press sequences modulo $10^9 + 7$ .

Examples3

Example 1
Input
```
2 1
1
```
Expected output
```
10
```
Example 2
Input
```
4 3
1 1 2
```
Expected output
```
1642
```
Example 3
Input
```
6 7
2 4 5 1 3 5 5
```
Expected output
```
6969072
```