Evolutionary biology research on $N$ neural tissues has traced history back to the dawn of human society, to a mysterious tribe called CCM.

Archaeological evidence suggests that CCM once possessed a highly prosperous civilization. However, the history of CCM seems to have mysteriously vanished overnight. Archaeologists recently excavated a site of CCM civilization ruins at the bottom of the Atlantic Ocean, which holds the hope of uncovering the mystery of the lost ancient CCM civilization.

At the center of the CCM ruins is a massive stone structure, which archaeologists call a pyramid. The pyramid has the following four properties:

1. The CCM pyramid is composed of identical $1 \times 1 \times 1$ unit cubic stone blocks.
2. The CCM pyramid consists of several layers. When viewed from directly above, the stone blocks of each layer form a connected component on the plane. Stone blocks in higher layers are supported by stone blocks in lower layers; there are no floating stone blocks.
3. Each layer of the CCM pyramid is strictly symmetric both horizontally and vertically, and the axes of symmetry for all layers coincide. The length/width decreases non-strictly from the horizontal/vertical axes of symmetry toward both ends.
4. The maximum length and maximum width of each layer of the CCM pyramid are equal, and both are even numbers (because the CCM people believed that even numbers represent good luck, while odd numbers bring misfortune).

Unfortunately, due to the passage of time, the pyramid in the ruins is incomplete and difficult to identify in its entirety. To reconstruct the actual situation of the CCM pyramid as much as possible, archaeologists have estimated the total number of stone blocks used in the CCM pyramid, the height of the pyramid, and the width of each layer through other evidence. They would like you to help calculate the number of possible pyramids that satisfy the above properties.

Input

The first line contains two integers: $n$ and $h$, representing the total number of stone blocks in the CCM pyramid and the height of the CCM pyramid, respectively.

Starting from the second line, there are $h$ lines, each containing an integer $l$, representing the maximum length (width) of each layer starting from the bottom layer. It is guaranteed that these values are non-strictly decreasing.

Output

Output a single integer representing the number of possible pyramids. Since the number of solutions can be very large, output the answer modulo $10^9+7$.

Examples

Input 1

36 3
6
4
2

Output 1

1

Input 2

44 2
6
4

Output 2

3

Note

The appearance of the pyramid in Example 1 when viewed from top to bottom: (numbers represent the height of that cell)

The appearance of the pyramid in Example 2 when viewed from top to bottom: (numbers represent the height of that cell)

Constraints

For 10% of the data, $h=1$. For 30% of the data, $n \le 200$, $l \le 10$, $h \le 5$. For 70% of the data, $n \le 800$, $l \le 20$, $h \le 8$. For 100% of the data, $n \le 1000$, $2 \le l \le 20$, $1 \le h \le 10$.