Problem Background

SHOI2014 day2t3

Problem Description

Neurobiological research on the evolution of organisms has traced history back to the beginning of human society, to a mysterious tribe called CCM.

Archaeological evidence shows that CCM once had a highly prosperous civilization. However, the history of CCM seems to have mysteriously disappeared overnight. Recently, archaeologists have excavated a CCM civilization site at the bottom of the Atlantic, hoping to uncover the mystery of the lost ancient CCM civilization.

At the center of the CCM ruins is a massive stone structure, which archaeologists call the 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, each layer's stone blocks form a connected block when viewed from directly above. Stone blocks in higher layers are supported by lower layers, with no blocks hanging in the air;
3. Each layer of the CCM pyramid strictly satisfies left-right symmetry and up-down symmetry, and all layers share the same symmetry axis, with the length/width non-strictly decreasing from the left-right/up-down symmetry axis to both ends;
4. The maximum length and width of each layer of the CCM pyramid are equal and are both even numbers (as the CCM people believe that even numbers represent good luck and odd numbers bring misfortune).

Unfortunately, the pyramid in the ruins is too ancient and has been damaged, making it difficult to discern the full picture. To restore the actual situation of the CCM pyramid as much as possible, archaeologists have estimated the total number of stone blocks used, the height of the pyramid, and the width of each layer based on other evidence. They would like you to calculate the number of possible pyramids that meet the above properties.

Input Format

The first line contains two integers $n, h$, representing the total number of stone blocks in the CCM pyramid and the height of the pyramid, respectively.
Starting from the second line, there are $h$ lines, each containing an integer $l$, representing the maximum length (width) of each layer from the bottom, guaranteed to be non-strictly decreasing.

Output Format

Output a single integer, representing the number of possible pyramids, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

36 3
6
4
2

Sample Output #1

1

Sample Input #2

44 2
6
4

Sample Output #2

3

Notes

For 10% of the data, $h=1$.

For 30% of the data, $n \leq 200, l \leq 10, h \leq 5$.

For 70% of the data, $n \leq 800, l \leq 20, h \leq 8$.

For 100% of the data, $n \leq 1000, 2 \leq l \leq 20, 1 \leq h \leq 10$.

见题面 Input 部分

见题面 Output 部分