P5215 [SHOI2014] Mysterious Pyramid

SHOI2014 day2t3.

Evolutionary biology research on neural tissue traces history back to the very beginning of human society, to a mysterious tribe called CCM. Archaeological evidence shows that CCM once had a highly prosperous civilization. However, CCM’s history seems to have mysteriously vanished overnight. Recently, archaeologists discovered a site of CCM civilization on the Atlantic seabed, and it is hoped that this can uncover the mystery of the lost ancient CCM civilization. At the center of the CCM site is a huge stone building, called a pyramid by archaeologists. The pyramid has the following four properties: 1. The CCM pyramid is made 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 blocks in each layer form a connected component on the plane. Every block in an upper layer has blocks in a lower layer directly beneath it for support, so no block is floating. 3. Each layer of the CCM pyramid strictly satisfies left-right symmetry and up-down symmetry, and the symmetry axes of all layers coincide. Along the left-right / up-down symmetry axes toward both ends, the length / width is non-increasing. 4. In each layer, the maximum length and the maximum width are equal, and both are even (because CCM people believed even numbers represent good luck, while odd numbers bring misfortune). Unfortunately, the pyramid in the ruins is too old and has been badly damaged, making it hard to recognize its full shape. In order to reconstruct the real CCM pyramid as much as possible, archaeologists estimated, from other evidence, the number of stone blocks used, the height of the pyramid, and the width of each layer. They want you to help compute how many possible pyramids satisfy the properties above.

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

Output one integer on a single line, representing the number of possible pyramids. Since the number of solutions may be very large, output the result modulo $10^9+7$.

For $10\%$ of the testdata, $h = 1$. For $30\%$ of the testdata, $n \leq 200, l \leq 10, h \leq 5$. For $70\%$ of the testdata, $n \leq 800, l \leq 20, h \leq 8$. For $100\%$ of the testdata, $n \leq 1000, 2 \leq l \leq 20, 1 \leq h \leq 10$.  Translated by ChatGPT 5